1166-Amazing Mazes

問題概要

（略）

考え方

最短経路問題．与えられる入力の形を上手く生かしてBFSすることが出来る．計算量はO(WH)となる．

実装(C++)

#include <iostream>
#include <vector>
#include <sstream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
#define REP(i,x)for(int i=0;i<(int)x;i++)
int h,w;
vector<string> MAP;
string in;
typedef pair<int,int> P;
int ac[800][800];
int dx[4]={-1,0,1,0},dy[4]={0,-1,0,1};
int solve(){
	memset(ac,0x7F,sizeof(ac));
	ac[0][0]=0;
	queue<P> que;
	que.push(P(0,0));
	while(!que.empty()){
		P t=que.front();que.pop();
		int now=ac[t.first][t.second];
		//cout<<t.first<<","<<t.second<<":"<<now<<endl;
		if(t.first==w-1&&t.second==h-1){
			return now/2+1;
		}
		REP(i,4){
			int nx=t.first+dx[i],ny=t.second+dy[i];
			if(nx%2==1&&ny%2==1)continue;
			if(nx<0||nx>=w||ny<0||ny>=h)continue;
			if(MAP[nx][ny]=='1')continue;
			if(ac[nx][ny]>now+1){
				ac[nx][ny]=now+1;
				que.push(P(nx,ny));
			}
		}
	}
	return 0;
}
int main() {
	for(;getline(cin,in);){
		stringstream ss(in);
		ss>>w>>h;
		if(w==0||h==0)break;
		MAP.clear();
		REP(i,h*2-1){
			getline(cin,in);
			MAP.push_back(in);
			if(i%2==0)MAP[i]=MAP[i]+" ";
		}
		w=w*2-1;
		h=h*2-1;
		swap(w,h);
		cout << solve() << endl;
	}
	return 0;
}