3934 迷

問題概要

5x5マスの迷路が与えられる。0は可能なマスであり、1は壁である。
上下左右に、壁のないマスに動ける。出発点は左上で、ゴールは右下のマスである。


スタートからゴールへの最短路を出力せよ。
最短路は一意に存在することが保証されている。

解法

幅優先探索+経路復元。
visitedの配列の代わりに前に来たマスの情報を持っておいて、ゴールから辿る。

ソースコード

int dy[]={-1,0,1,0},dx[]={0,-1,0,1};
int m[5][5],p[5][5],ax[30],ay[30],na;

int main(){
	rep(i,5)rep(j,5)scanf("%d",m[i]+j),p[i][j]=-1;
	queue<int> Q; Q.push(0);
	while(!Q.empty()){
		int y=Q.front()/5,x=Q.front()%5; Q.pop();
		rep(d,4){
			int ny=y+dy[d],nx=x+dx[d];
			if(ny<0||ny>4||nx<0||nx>4||m[ny][nx]||p[ny][nx]>=0)continue;
			Q.push(ny*5+nx); p[ny][nx]=d;
			if(ny==4&&nx==4)goto END;
		}
	}
	END:
	for(int y=4,x=4;;){
		ay[na]=y; ax[na++]=x;
		if(x==0&&y==0)break;
		
		int ny=y-dy[p[y][x]],nx=x-dx[p[y][x]];
		y=ny; x=nx;
	}
	rep(i,na)printf("(%d, %d)\n",ay[na-1-i],ax[na-1-i]);
	
	return 0;
}