AOJ 1166 Amazing Mazes
問題
解法
寝落ちして、1時ぐらいに解いた。一発AC。 BFSで解けます。下か上に行く時はin[y*2±1][x]が1なら進めない。左右はin[y*2][x]が1なら進めないってやっていく。
コード
int w, h, maze[128][128], dy[] = {0,-1,0,1}, dx[] = {-1,0,1,0};; int main(){ while(scanf("%d%d", &w, &h) && w+h){ rep(i, 2*h-1){ rep(j, (i%2)?w:w-1) scanf("%d", &maze[i][j]); } map<pi, int>m; queue<pi>q; q.push(MP(0, 0)); m[MP(0, 0)] = 1; int res = 1; while(!q.empty()){ int qsize = (int)q.size(); rep(i, qsize){ pi now = q.front(); q.pop(); rep(d, 4){ int ny = now.Y + dy[d], nx = now.X + dx[d]; if(ny < 0 || nx < 0 || ny >= h || nx >= w || m.count(MP(ny,nx))) continue; if(d == 0){ if(maze[now.Y*2][now.X-1]) continue; }else if(d == 1){ if(maze[now.Y*2-1][now.X]) continue; }else if(d == 2){ if(maze[now.Y*2][now.X]) continue; }else if(d == 3){ if(maze[now.Y*2+1][now.X]) continue; } m[MP(ny, nx)] = 1; q.push(MP(ny, nx)); if(ny == h-1 && nx == w-1){ printf("%d\n", res+1); goto e; } } } res++; } puts("0"); e:; } return 0; }
dのループのところは三項演算子とかでもっときれいにかけるし、 フォーマットといじってやると楽に出来たりするらしい