『鐘万北』08.ダイナミックプランニング:シングルステップ(Jumpgame)

1049 ワード
鐘万北 algorithm algospot recursion dynamicprogramming テキストリンク
下にゲームボードがあり、n×nサイズのメッシュに1から9まで整数を図に示すように書きます.このゲームの目的は、ゲームボードの左上から、ゲーム波の右下に到達することです.
各グリッドの数字は、下または右に移動できます.

コード8.4
int n, board[100][100];
bool jump(int y, int x) {
	if (y >= n || x >= n) return false;

	if (y == n - 1 && x == n - 1) return true;

	int jumpSize = board[y][x];
	return jump(y + jumpSize, x) || jump(y, x + jumpSize);
}
  • ベースケース:ゲームボードを離れるとfalse、最後のグリッドに達するとtrue
  • 現在のセルの数値=jumpSizeを保存した後、右に曲がってjump(y,x+jumpSize)に戻り、下にy+jumpSize,x)のtrue値に戻ります.
  • ジャンプ()は、入力が固定されている場合、その結果が常に同じ関数である参照透明関数であるため、コメントを適用することができる.
    • int n, board[100][100];
int cache[100][100];

int  jump2(int y, int x) {
	if (y >= n || x >= n) return 0;

	if (y == n - 1 && x == n - 1) return 1;

	int& ret = cache[y][x];
	if (ret != -1) return ret;
	int jumpSize = board[y][x];
	return ret=jump2(y + jumpSize, x) || jump2(y, x + jumpSize);
}
    21-06-19春コース初日
    非ブロックキューConcurrentLinkedQueue