問題文:404 Not Found
フォーマット弄って幅優先でやりました。これが一番楽だと思った。
フォーマットうけつけが問題な問題。勝手に盤面拡大してるので、出力するのは/2したりしてゴニョる。
迷図と命ず[Amazing Mazes](渾身のギャグ)
こんなイメージ↓
#include <iostream> #include <queue> using namespace std; #define rep(i,n) for(int i=0;i<n;i++) struct NODE{ int x,y,d; NODE(int a,int b,int c){x=a , y=b, d=c;} }; static const int dx[] = {-1,0,1,0} , dy[] = {0,-1,0,1}; int main(){ int W,H; while(cin >> W >> H , H){ int ans = 0; bool data[62][62] = {0}; rep(i,62)rep(j,62)data[i][j] = 1; rep(i,H*2-1)rep(j,W*2-1)data[i+1][j+1] = 0; // マップ生成 rep(i,2*H-1){ if(i%2==0){ rep(j,W-1){ bool a; cin >> a; data[i+0][j*2+2] |= a; data[i+1][j*2+2] |= a; data[i+2][j*2+2] |= a; } }else{ rep(j,W){ bool a; cin >> a; data[i+1][j*2+0] |= a; data[i+1][j*2+1] |= a; data[i+1][j*2+2] |= a; } } } // 幅優先探索 bool done[62][62] = {0}; queue<NODE> Q; Q.push(NODE(1,1,0)); while(Q.size()){ NODE q = Q.front(); Q.pop(); if(done[q.y][q.x])continue; else done[q.y][q.x] = true; if(q.x == W*2-1 && q.y == H*2-1){ ans = (q.d+2)/2; break; } rep(i,4){ int tx = dx[i] + q.x , ty = dy[i] + q.y; if(data[ty][tx] == true)continue; Q.push(NODE(tx,ty,q.d+1)); } } cout << ans << endl; } }