AOJ - Problem 1166 : Amazing Mazes

• 問題文

幅優先探索でスタートからゴールまでの最短経路を求める問題です。
入力の数が偶数行と奇数行で異なり、入力がしんどい問題でした。
2年前はきちんとコードが書けなかったのでそう考えると私も成長しているのかもしれません。

#include <iostream>
#include <map>
#include <queue>
using namespace std;
typedef pair<int,int> P;

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

int solve(int a[100][100]){
	int d[100][100] = {0};
	d[1][1] = 1;

	P sp(1,1);
	queue<P> q;
	q.push( sp );

	while( !q.empty() ){
		P p = q.front();
		q.pop();
		int x = p.first;
		int y = p.second;
		int cnt = d[y][x];

		if( x == w*2-1 && y == h*2-1 ) break;

		for(int i=0 ; i < 4 ; i++ ){
			int mx = x + dx[i];
			int my = y + dy[i];
			int nx = mx + dx[i];
			int ny = my + dy[i];
			if( nx < 0 || ny < 0 || nx > w*2 || ny > h*2 ) continue;
			
			if( a[my][mx] == 0 && d[ny][nx] == 0 ){
				P np( nx , ny );
				q.push( np );
				d[ny][nx] = cnt+1;
			}
		}
	}
	return d[h*2-1][w*2-1];
}

int main(){
	while( cin >> w >> h , w||h ){
		int a[100][100] = {0};
		for(int x=0 ; x <= w*2 ; x++ ){
			a[0][x] = a[h*2][x] = 1;
		}
		for(int y=0 ; y <= h*2 ; y++ ){
			a[y][0] = a[y][w*2] = 1;
		}

		for(int y=0 ; y < (h*2-1) ; y++ ){
			if( y%2 == 0 ){
				for(int x=0 ; x < w-1 ; x++ ){
					//(x,y) => (2x+2,y+1);
					cin >> a[y+1][2*x+2];
				}
			}else{
				for(int x=0 ; x < w ; x++ ){
					//(x,y) => (2x+1,y+1);
					cin >> a[y+1][2*x+1];
				}
			}
		}
		cout << solve( a ) << endl;
	}
}