AOJ Problem 1166 : Amazing Mazes

問題文: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;
	}
}