Curling 2.0 - kyoupuro @ ウィキ

1144 : Curling 2.0

問題文

解説

スタートからゴールまでの最小の移動回数を出力する。
上下左右の4方向に対して全探索を行えばいい。移動の上限が10なので、計算回数は気にしなくてもいいだろう。
ポイントは「隣に障害物がある場合はその方向に移動が出来ない」ことと、「障害物を消して再帰関数を呼び出したあとに、また障害物を復活させる」ことぐらいかな？

プログラム

C

C++

...

#include <iostream>
using namespace std;
 
int w, h;
int map[20+1][20+1];
int mini;
 
void solve(int ny, int nx, int move) {
	if (move == 10) {
		return;
	}

	//右
	if (nx+1 < w && map[ny][nx+1] != 1) {
		for (int i = 1; ; i++) {
			if (nx+i >= w) break;
			if (map[ny][nx+i] == 0 || map[ny][nx+i] == 2) {
				continue;
			} else if (map[ny][nx+i] == 1) {
				map[ny][nx+i] = 0;
				solve(ny, nx+i-1, move+1);
				map[ny][nx+i] = 1;
				break;
			} else {
				if (mini > move+1) mini = move+1;
				break;
			}
		}
	}
	
	//下
	if (ny+1 < h && map[ny+1][nx] != 1) {
		for (int i = 1; ; i++) {
			if (ny+i >= h) break;
			if (map[ny+i][nx] == 0 || map[ny+i][nx] == 2) {
				continue;
			} else if (map[ny+i][nx] == 1) {
				map[ny+i][nx] = 0;
				solve(ny+i-1, nx, move+1);
				map[ny+i][nx] = 1;
				break;
			} else {
				if (mini > move+1) mini = move+1;
				break;
			}
		}
	}

	//左
	if (nx-1 >= 0 && map[ny][nx-1] != 1) {
		for (int i = 1; ; i++) {
			if (nx-i < 0) break;
			if (map[ny][nx-i] == 0 || map[ny][nx-i] == 2) {
				continue;
			} else if (map[ny][nx-i] == 1) {
				map[ny][nx-i] = 0;
				solve(ny, nx-i+1, move+1);
				map[ny][nx-i] = 1;
				break;
			} else {
				if (mini > move+1) mini = move+1;
				break;
			}
		}
	}

	//上
	if (ny-1 >= 0 && map[ny-1][nx] != 1) {
		for (int i = 1; ; i++) {
			if (ny-i < 0) break;
			if (map[ny-i][nx] == 0 || map[ny-i][nx] == 2) {
				continue;
			} else if (map[ny-i][nx] == 1) {
				map[ny-i][nx] = 0;
				solve(ny-i+1, nx, move+1);
				map[ny-i][nx] = 1;
				break;
			} else {
				if (mini > move+1) mini = move+1;
				break;
			}
		}
	}

	return;
}

int main() {
	while (cin >> w >> h, w || h) {
		int start[2];
		for (int i = 0; i < h; i++) {
			for (int j = 0; j < w; j++) {
				cin >> map[i][j];
				if (map[i][j] == 2) {
					start[0] = i;
					start[1] = j;
				}
			}
		}

		mini = 11;
		solve(start[0], start[1], 0);

		if (mini == 11) cout << -1 << endl;
		else cout << mini << endl;
	}
}

Java