2010 ICPC国内予選 B.迷図と命ず

問題概要

グリッド上に描かれた迷路が与えられる。このとき、ゴールまでの最短の道のりを求めよ。
迷路は各グリッドの壁の情報によって与えられる。

解法

入力が壁の情報によってなのでややこしい。
座標を2倍するか、判定をがんばる。

判定を頑張る場合、左右に動くときは縦向きの壁とぶつからないか、上下に動くときは横向きの壁とぶつからないかを判定すればいい。

最短距離は幅優先探索などで適当に。

ソースコード

判定を頑張ったコード。

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};

int w,h;
bool tate[40][40],yoko[40][40];

int main(){
	while(cin>>w>>h,w)
	{
		rep(i,2*h-1)
		{
			if(i%2==0)rep(j,w-1)cin>>tate[i][j];
			else rep(j,w)cin>>yoko[i][j];
		}
		
		bool V[40][40]={0};
		queue<pair<int,pi> >Q; Q.push(mp(1,mp(0,0)));
		int ans=inf;
		while(!Q.empty())
		{
			int x=Q.front().second.second,y=Q.front().second.first;
			int cc=Q.front().first; Q.pop();
			
			if(x==w-1&&y==h-1)
			{
				ans=cc; break;
			}
			
			rep(d,4)
			{
				int ny=y+dy[d],nx=x+dx[d];
				if(ny<0||nx<0||ny>=h||nx>=w)continue;
				if(d==0&&yoko[y*2-1][x]||
					d==1&&tate[y*2][x]||
					d==2&&yoko[y*2+1][x]||
					d==3&&tate[y*2][x-1])continue;
				if(!V[ny][nx])Q.push(mp(cc+1,mp(ny,nx))),V[ny][nx]=1;
			}
		}
		cout<<(ans==inf?0:ans)<<endl;
	}
	return 0;
}