空欄が多いですね．ヒントにあるように最初の移動で場合分けして漸化式を立式し解きます．