Source Code

Problem: 3083  User: sunyuanshuai 
Memory: N/A  Time: N/A 
Language: C++  Result: Wrong Answer 

Source Code 
#include<iostream>
#include<stack>
#include<queue>
using namespace std;

struct Point
{
	int x,y;
	int direction;//决定下一的左右
};

Point create(int a,int b,int c=0)
{
	Point p;
	p.x=a;
	p.y=b;
	p.direction=c;
	return p;
}
int main()
{
	int num;
	cin>>num;
	while(num--)
	{
		Point start,end;
		int r,c,i,j,maze_l[40][40]={0},maze_r[40][40]={0},maze_b[40][40]={0};
		cin>>c>>r;
		char ch;//迷宫中0同，1不通,-1表示开始，-2表示结束
		for(i=0;i<r;i++)
		{
			for(j=0;j<c;j++)
			{
				cin>>ch;
				if(ch=='#')
				{	
					maze_l[i][j]=1;
					maze_r[i][j]=1;
					maze_b[i][j]=1;
				}
				else if(ch=='.')
				{
					maze_l[i][j]=0;
					maze_r[i][j]=0;
					maze_b[i][j]=0;
				}
				else if(ch=='S')
				{
					maze_l[i][j]=-1;
					maze_r[i][j]=-1;
					maze_b[i][j]=-1;
					start=create(i,j);
				}
				else if(ch=='E')
				{
					maze_l[i][j]=-2;
					maze_r[i][j]=-2;
					maze_b[i][j]=-2;
					end=create(i,j);
				}
			}
		}

		int length_l=1,length_r=1,length_b=1;

		int a,b;
		//向左深搜
		stack<Point> st_l;
		if(start.x==0)
			start.direction=1;
		else if(start.x==r-1)
			start.direction=2;
		else if(start.y==0)
			start.direction=3;
		else if(start.y==c-1)
			start.direction=4;
		st_l.push(start);
		while(1)
		{
			if(st_l.empty())
				break;
			if(st_l.top().direction==1)
			{
				if((maze_l[st_l.top().x][st_l.top().y+1]==0&&st_l.top().y!=c-1)||maze_l[st_l.top().x][st_l.top().y+1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y+1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y+1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y+1,3));
					length_l++;
				}
				else if((maze_l[st_l.top().x+1][st_l.top().y]==0&&st_l.top().x!=r-1)||maze_l[st_l.top().x+1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x+1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x+1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x+1,st_l.top().y,1));
					length_l++;
				}
				else if((maze_l[st_l.top().x][st_l.top().y-1]==0&&st_l.top().y!=0)||maze_l[st_l.top().x][st_l.top().y-1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y-1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y-1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y-1,4));
					length_l++;
				}
				else if((maze_l[st_l.top().x-1][st_l.top().y]==0&&st_l.top().x!=0)||maze_l[st_l.top().x-1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x-1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x-1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x-1,st_l.top().y,2));
					length_l++;
				}
				else
				{
					length_l++;
					a=st_l.top().x,b=st_l.top().y;
					st_l.pop();
					if(st_l.top().x>a)
						st_l.top().direction=1;
					else if(st_l.top().x<a)
						st_l.top().direction=2;
					else if(st_l.top().y>b)
						st_l.top().direction=3;
					else if(st_l.top().y<b)
						st_l.top().direction=4;
				}
			}
			else if(st_l.top().direction==2)
			{
				if((maze_l[st_l.top().x][st_l.top().y-1]==0&&st_l.top().y!=0)||maze_l[st_l.top().x][st_l.top().y-1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y-1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y-1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y-1,4));
					length_l++;
				}
				else if((maze_l[st_l.top().x-1][st_l.top().y]==0&&st_l.top().x!=0)||maze_l[st_l.top().x-1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x-1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x-1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x-1,st_l.top().y,2));
					length_l++;
				}
				else if((maze_l[st_l.top().x][st_l.top().y+1]==0&&st_l.top().y!=c-1)||maze_l[st_l.top().x][st_l.top().y+1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y+1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y+1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y+1,3));
					length_l++;
				}
				else if((maze_l[st_l.top().x+1][st_l.top().y]==0&&st_l.top().x!=r-1)||maze_l[st_l.top().x+1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x+1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x+1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x+1,st_l.top().y,1));
					length_l++;
				}
				else
				{
					length_l++;
					a=st_l.top().x,b=st_l.top().y;
					st_l.pop();
					if(st_l.top().x>a)
						st_l.top().direction=1;
					else if(st_l.top().x<=a)
						st_l.top().direction=2;
					else if(st_l.top().y>b)
						st_l.top().direction=3;
					else if(st_l.top().y<b)
						st_l.top().direction=4;
				}
			}
			else if(st_l.top().direction==3)
			{
				 if((maze_l[st_l.top().x-1][st_l.top().y]==0&&st_l.top().x!=0)||maze_l[st_l.top().x-1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x-1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x-1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x-1,st_l.top().y,2));
					length_l++;
				}
				else if((maze_l[st_l.top().x][st_l.top().y+1]==0&&st_l.top().y!=c-1)||maze_l[st_l.top().x][st_l.top().y+1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y+1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y+1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y+1,3));
					length_l++;
				}
				else if((maze_l[st_l.top().x+1][st_l.top().y]==0&&st_l.top().x!=r-1)||maze_l[st_l.top().x+1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x+1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x+1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x+1,st_l.top().y,1));
					length_l++;
				}
				else if((maze_l[st_l.top().x][st_l.top().y-1]==0&&st_l.top().y!=0)||maze_l[st_l.top().x][st_l.top().y-1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y-1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y-1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y-1,4));
					length_l++;
				}
				else
				{
					length_l++;
					a=st_l.top().x,b=st_l.top().y;
					st_l.pop();
					if(st_l.top().x>a)
						st_l.top().direction=1;
					else if(st_l.top().x<=a)
						st_l.top().direction=2;
					else if(st_l.top().y>b)
						st_l.top().direction=3;
					else if(st_l.top().y<b)
						st_l.top().direction=4;
				}
			}
			else if(st_l.top().direction==4)
			{
				if((maze_l[st_l.top().x+1][st_l.top().y]==0&&st_l.top().x!=r-1)||maze_l[st_l.top().x+1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x+1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x+1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x+1,st_l.top().y,1));
					length_l++;
				}
				else if((maze_l[st_l.top().x][st_l.top().y-1]==0&&st_l.top().y!=0)||maze_l[st_l.top().x][st_l.top().y-1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y-1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y-1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y-1,4));
					length_l++;
				}
				else if((maze_l[st_l.top().x-1][st_l.top().y]==0&&st_l.top().x!=0)||maze_l[st_l.top().x-1][st_l.top().y]==-2)
				{
					if(maze_l[st_l.top().x-1][st_l.top().y]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x-1][st_l.top().y]=1;
					st_l.push(create(st_l.top().x-1,st_l.top().y,2));
					length_l++;
				}
				else if((maze_l[st_l.top().x][st_l.top().y+1]==0&&st_l.top().y!=c-1)||maze_l[st_l.top().x][st_l.top().y+1]==-2)
				{
					if(maze_l[st_l.top().x][st_l.top().y+1]==-2)
					{
						length_l++;
						break;
					}
					maze_l[st_l.top().x][st_l.top().y+1]=1;
					st_l.push(create(st_l.top().x,st_l.top().y+1,3));
					length_l++;
				}
				else
				{
					length_l++;
					a=st_l.top().x,b=st_l.top().y;
					st_l.pop();
					if(st_l.top().x>a)
						st_l.top().direction=1;
					else if(st_l.top().x<=a)
						st_l.top().direction=2;
					else if(st_l.top().y>b)
						st_l.top().direction=3;
					else if(st_l.top().y<b)
						st_l.top().direction=4;
				}
			}
		}

		//向右深搜
		stack<Point> st_r;
		st_r.push(start);
		while(1)
		{
			if(st_r.empty())
				break;
			if(st_r.top().direction==1)
			{
				if((maze_r[st_r.top().x][st_r.top().y-1]==0&&st_r.top().y!=0)||maze_r[st_r.top().x][st_r.top().y-1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y-1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y-1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y-1,4));
					length_r++;
				}
				else if((maze_r[st_r.top().x-1][st_r.top().y]==0&&st_r.top().x!=0)||maze_r[st_r.top().x-1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x-1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x-1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x-1,st_r.top().y,2));
					length_r++;
				}
				else if((maze_r[st_r.top().x][st_r.top().y+1]==0&&st_r.top().y!=c-1)||maze_r[st_r.top().x][st_r.top().y+1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y+1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y+1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y+1,3));
					length_r++;
				}
				else if((maze_r[st_r.top().x+1][st_r.top().y]==0&&st_r.top().x!=r-1)||maze_r[st_r.top().x+1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x+1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x+1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x+1,st_r.top().y,1));
					length_r++;
				}
				else
				{
					length_r++;
					a=st_r.top().x,b=st_r.top().y;
					st_r.pop();
					if(st_r.top().x>a)
						st_r.top().direction=1;
					else if(st_r.top().x<=a)
						st_r.top().direction=2;
					else if(st_r.top().y>b)
						st_r.top().direction=3;
					else if(st_r.top().y<b)
						st_r.top().direction=4;
				}
			}
			else if(st_r.top().direction==2)
			{
				if((maze_r[st_r.top().x][st_r.top().y+1]==0&&st_r.top().y!=c-1)||maze_r[st_r.top().x][st_r.top().y+1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y+1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y+1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y+1,3));
					length_r++;
				}
				else if((maze_r[st_r.top().x+1][st_r.top().y]==0&&st_r.top().x!=r-1)||maze_r[st_r.top().x+1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x+1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x+1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x+1,st_r.top().y,1));
					length_r++;
				}
				else if((maze_r[st_r.top().x][st_r.top().y-1]==0&&st_r.top().y!=0)||maze_r[st_r.top().x][st_r.top().y-1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y-1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y-1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y-1,4));
					length_r++;
				}
				else if((maze_r[st_r.top().x-1][st_r.top().y]==0&&st_r.top().x!=0)||maze_r[st_r.top().x-1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x-1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x-1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x-1,st_r.top().y,2));
					length_r++;
				}
				else
				{
					length_r++;
					a=st_r.top().x,b=st_r.top().y;
					st_r.pop();
					if(st_r.top().x>a)
						st_r.top().direction=1;
					else if(st_r.top().x<=a)
						st_r.top().direction=2;
					else if(st_r.top().y>b)
						st_r.top().direction=3;
					else if(st_r.top().y<b)
						st_r.top().direction=4;
				}
			}
			else if(st_r.top().direction==3)
			{
				if((maze_r[st_r.top().x+1][st_r.top().y]==0&&st_r.top().x!=r-1)||maze_r[st_r.top().x+1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x+1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x+1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x+1,st_r.top().y,1));
					length_r++;
				}
				else if((maze_r[st_r.top().x][st_r.top().y-1]==0&&st_r.top().y!=0)||maze_r[st_r.top().x][st_r.top().y-1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y-1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y-1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y-1,4));
					length_r++;
				}
				else if((maze_r[st_r.top().x-1][st_r.top().y]==0&&st_r.top().x!=0)||maze_r[st_r.top().x-1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x-1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x-1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x-1,st_r.top().y,2));
					length_r++;
				}
				else if((maze_r[st_r.top().x][st_r.top().y+1]==0&&st_r.top().y!=c-1)||maze_r[st_r.top().x][st_r.top().y+1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y+1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y+1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y+1,3));
					length_r++;
				}
				else
				{
					length_r++;
					a=st_r.top().x,b=st_r.top().y;
					st_r.pop();
					if(st_r.top().x>a)
						st_r.top().direction=1;
					else if(st_r.top().x<=a)
						st_r.top().direction=2;
					else if(st_r.top().y>b)
						st_r.top().direction=3;
					else if(st_r.top().y<b)
						st_r.top().direction=4;
				}
			}
			if(st_r.top().direction==4)
			{
				if((maze_r[st_r.top().x-1][st_r.top().y]==0&&st_r.top().x!=0)||maze_r[st_r.top().x-1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x-1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x-1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x-1,st_r.top().y,2));
					length_r++;
				}
				else if((maze_r[st_r.top().x][st_r.top().y+1]==0&&st_r.top().y!=c-1)||maze_r[st_r.top().x][st_r.top().y+1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y+1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y+1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y+1,3));
					length_r++;
				}
				else if((maze_r[st_r.top().x+1][st_r.top().y]==0&&st_r.top().x!=r-1)||maze_r[st_r.top().x+1][st_r.top().y]==-2)
				{
					if(maze_r[st_r.top().x+1][st_r.top().y]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x+1][st_r.top().y]=1;
					st_r.push(create(st_r.top().x+1,st_r.top().y,1));
					length_r++;
				}
				else if((maze_r[st_r.top().x][st_r.top().y-1]==0&&st_r.top().y!=0)||maze_r[st_r.top().x][st_r.top().y-1]==-2)
				{
					if(maze_r[st_r.top().x][st_r.top().y-1]==-2)
					{
						length_r++;
						break;
					}
					maze_r[st_r.top().x][st_r.top().y-1]=1;
					st_r.push(create(st_r.top().x,st_r.top().y-1,4));
					length_r++;
				}
				else
				{
					length_r++;
					a=st_r.top().x,b=st_r.top().y;
					st_r.pop();
					if(st_r.top().x>a)
						st_r.top().direction=1;
					else if(st_r.top().x<=a)
						st_r.top().direction=2;
					else if(st_r.top().y>b)
						st_r.top().direction=3;
					else if(st_r.top().y<b)
						st_r.top().direction=4;
				}
			}
		}




		//广搜球最短路径长度
		Point flag=create(-1,-1);
		queue<Point> qu;
		maze_b[start.x][start.y]=1;
		qu.push(start);
		qu.push(flag);
		while(1)
		{
			if(maze_b[qu.front().x][qu.front().y+1]==-2)
			{
				length_b++;
				break;
			}
			if(maze_b[qu.front().x][qu.front().y+1]==0&&qu.front().y!=c-1)
			{
				maze_b[qu.front().x][qu.front().y+1]=1;
				qu.push(create(qu.front().x,qu.front().y+1));
			}
			if(maze_b[qu.front().x+1][qu.front().y]==-2)
			{
				length_b++;
				break;
			}
			if(maze_b[qu.front().x+1][qu.front().y]==0&&qu.front().x!=r-1)
			{
				maze_b[qu.front().x+1][qu.front().y]=1;
				qu.push(create(qu.front().x+1,qu.front().y));
			}
			if(maze_b[qu.front().x][qu.front().y-1]==-2)
			{
				length_b++;
				break;
			}
			if(maze_b[qu.front().x][qu.front().y-1]==0&&qu.front().y!=0)
			{
				maze_b[qu.front().x][qu.front().y-1]=1;
				qu.push(create(qu.front().x,qu.front().y-1));
			}
			if(maze_b[qu.front().x-1][qu.front().y]==-2)
			{
				length_b++;
				break;
			}
			if(maze_b[qu.front().x-1][qu.front().y]==0&&qu.front().x!=0)
			{
				maze_b[qu.front().x-1][qu.front().y]=1;
				qu.push(create(qu.front().x-1,qu.front().y));
			}
			qu.pop();
			if(qu.front().x==-1&&qu.front().y==-1)
			{
				length_b++;
				qu.pop();
				qu.push(flag);
				if(qu.size()==0)
					break;
			}
		}

		cout<<length_l<<" "<<length_r<<" "<<length_b<<endl;
	}
	return 0;
}