记录编号	51682	评测结果	AAAAAAAAAA
题目名称	穿越栅栏	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.008 s
提交时间	2012-12-28 17:56:48	内存使用	1.17 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
const int INF=0xffffff;
const int MAXH=1000,MAXW=100;
char board[MAXH][MAXW]={0};
int h,w;//h行w列
int leng1[MAXH][MAXW]={0},leng2[MAXH][MAXW]={0};
void BFS_point(int x,int y,int p,int leng[MAXH][MAXW]){
	queue<pair<int,int> > s;
	int x1,y1,temp;
	s.push(make_pair(x,y)),leng[x][y]=p;
	while(!s.empty()){
		x1=s.front().first,y1=s.front().second,s.pop();
		if(board[x1+1][y1]==' '&&x1<2*h&&leng[x1+1][y1]==INF){			
			s.push(make_pair(x1+1,y1));
			if(board[x1+1][y1-1]=='+') temp=0;
			else temp=1;
			if(leng[x1+1][y1]>leng[x1][y1]+temp) leng[x1+1][y1]=leng[x1][y1]+temp;
		}
		if(board[x1-1][y1]==' '&&x1>0&&leng[x1-1][y1]==INF){
			s.push(make_pair(x1-1,y1));
			if(board[x1-1][y1-1]=='+') temp=0;
			else temp=1;
			if(leng[x1-1][y1]>leng[x1][y1]+temp) leng[x1-1][y1]=leng[x1][y1]+temp;
		}
		if(board[x1][y1+1]==' '&&y1<2*w&&leng[x1][y1+1]==INF){
			s.push(make_pair(x1,y1+1));
			if(board[x1-1][y1+1]=='+') temp=0;
			else temp=1;
			if(leng[x1][y1+1]>leng[x1][y1]+temp) leng[x1][y1+1]=leng[x1][y1]+temp;
		}
		if(board[x1][y1-1]==' '&&y1>0&&leng[x1][y1-1]==INF){
			s.push(make_pair(x1,y1-1));
			if(board[x1-1][y1-1]=='+') temp=0;
			else temp=1;
			if(leng[x1][y1-1]>leng[x1][y1]+temp) leng[x1][y1-1]=leng[x1][y1]+temp;
		}
	}
}
void BFS(void){
	int i,j,flag=false;
	for(i=0;i<=2*h;i++){
		if(board[i][0]==' '){
			if(!flag) BFS_point(i,0,0,leng1),flag=true;
			else BFS_point(i,0,0,leng2);
		}
	}
	for(i=0;i<=2*h;i++){
		if(board[i][2*w]==' '){
			if(!flag) BFS_point(i,2*w,0,leng1),flag=true;
			else BFS_point(i,2*w,0,leng2);
		}
	}
	for(j=0;j<=2*w;j++){
		if(board[0][j]==' '){
			if(!flag) BFS_point(0,j,0,leng1),flag=true;
			else BFS_point(0,j,0,leng2);
		}
	}
	for(j=0;j<=2*w;j++){
		if(board[2*h][j]==' '){
			if(!flag) BFS_point(2*h,j,0,leng1),flag=true;
			else BFS_point(2*h,j,0,leng2);
		}
	}
}
void input(void){
	scanf("%d%d",&w,&h);
	int i,j;
	char ch[MAXW]={0};
	cin.getline(ch,MAXW);
	for(i=0;i<=2*h;i++){
		cin.getline(ch,MAXW);
		for(j=0;j<=2*w;j++){
			board[i][j]=ch[j];
			leng1[i][j]=INF,leng2[i][j]=INF;
		}
	}
}
int find(void){
	int max=-1,i,j,temp;
	for(i=0;i<=2*h;i++){
		for(j=0;j<=2*w;j++){
			temp=(leng1[i][j]<leng2[i][j])?leng1[i][j]:leng2[i][j];
			if(temp!=INF&&temp>max) max=temp;
		}
	}
	return max;
}
int main(){
	freopen("maze1.in","r",stdin);
	freopen("maze1.out","w",stdout);
	input();
	BFS();
	printf("%d\n",find());
	return 0;
}