AOJ 1144 Curling 2.0
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1144&lang=jp
日本語。
解法
DFSで解く。四方向見て、進めるなら進む。盤面の外に行ったら次っていう感じでまわしてく。
コード
int w, h; int board[20][20]; int dx[] = {0,-1,0,1}, dy[] = {-1,0,1,0}; int dfs(int y, int x, int c){ int ret = INF; if(c >= 10) return ret; rep(d, 4){ int ny = y+dy[d], nx = x+dx[d]; if(ny < 0 || nx < 0 || ny >= h || nx >= w) continue; if(board[ny][nx] == 1) continue; if(board[ny][nx] == 3) return c+1; while(true){ ny += dy[d]; nx += dx[d]; if(ny < 0 || nx < 0 || ny >= h || nx >= w) break;; if(board[ny][nx] == 3) return c+1; if(board[ny][nx] == 1){ board[ny][nx] = 0; ret = min(ret, dfs(ny-dy[d], nx-dx[d], c+1)); board[ny][nx] = 1; break; } } } return ret; } int main(){ while(scanf("%d%d", &w, &h) && w+h){ rep(i, h) rep(j, w) scanf("%d", &board[i][j]); int y, x; rep(i, h) rep(j, w) if(board[i][j] == 2) y = i, x = j; board[y][x] = 0; int res = dfs(y, x, 0); printf("%d\n", res==INF?-1:res); } return 0; }