AOJ_1166

AOJ_1166.cpp

#include <iostream>
#include <queue>
#include <map>
#include <utility>

using namespace std;
int data[70][31]={};
int ans[31][31]={1};
int dx[4]={-1,0,1,0};
int dy[4]={0,-1,0,1};

int main(){
	int w,h;
	while(cin>>w>>h){
		if(!w && !h){
			break;
		}
		for(int i=0;i<h;i++){
			for(int j=0;j<w;j++){
				//visit[i][j]=0;
				ans[i][j]=0;
			}
		}
		ans[0][0]=1;
		for(int i=0;i<2*h-1;i++){
			if(i%2==0){
				for(int j=0;j<w-1;j++){
					cin>>data[i][j];
				}
			}
			else{
				for(int j=0;j<w;j++){
					cin>>data[i][j];
				}
			}
		}

		/*for(int i=0;i<2*h-1;i++){
			for(int j=0;j<w;j++){
				cout<<data[i][j]<<" ";
			}
			cout<<endl;
		}*/
		//---input---

		queue<pair<int,int> > q;
		q.push(make_pair(0,0));
		pair<int,int> now;
		while(!q.empty()){
			now=q.front();
			q.pop();
			if(h-1==now.first && w-1==now.second){
				break;
			}
			//cout<<now.first<<" "<<now.second<<" "<<visit[now.first][now.second]<<endl;
			/*if(visit[now.first][now.second]){
				//cout<<"visited"<<endl;
				continue;
			}*/
			//visit[now.first][now.second]=1;
			for(int i=0;i<4;i++){
				if(ans[now.first+dy[i]][now.second+dx[i]]==0){
					if(i==0 && data[2*now.first][now.second-1]==0 && 0<=now.second+dx[i]){
						//cout<<"hidari"<<endl;
						q.push(make_pair(now.first+dy[i],now.second+dx[i]));
						ans[now.first+dy[i]][now.second+dx[i]]=ans[now.first][now.second]+1;
					}
					else if(i==1 && data[2*now.first-1][now.second]==0 && 0<=now.first+dy[i]){
						//cout<<"ue"<<endl;
						q.push(make_pair(now.first+dy[i],now.second+dx[i]));
						ans[now.first+dy[i]][now.second+dx[i]]=ans[now.first][now.second]+1;
					}
					else if(i==2  && data[2*now.first][now.second]==0 && w>now.second+dx[i]){
						//cout<<"migi"<<endl;
						q.push(make_pair(now.first+dy[i],now.second+dx[i]));
						ans[now.first+dy[i]][now.second+dx[i]]=ans[now.first][now.second]+1;
					}
					else if(i==3 && data[2*now.first+1][now.second]==0 && h>now.first+dy[i]){
						//cout<<"sita"<<endl;
						q.push(make_pair(now.first+dy[i],now.second+dx[i]));
						ans[now.first+dy[i]][now.second+dx[i]]=ans[now.first][now.second]+1;
					}
				}
			}
		}
		cout<<ans[h-1][w-1]<<endl;
	}
	return 0;
}