Description
AC小公主很喜欢设计迷宫，她设计的迷宫只有两个口，一个入口，一个出口。但小公主有时候很调皮，她会让挑战者走不出迷宫。现在给你AC小公主的迷宫请你判断挑战者能否成功从出口走出迷宫，迷宫包证边界为障碍物，只有两个不同的入口。
“#”代表障碍物，“*”代表可走的路。
Input
输入有多组，每组输入两个正整数n，m（ 2 < n < m < 1000）。
接下来n行，每行有m个字符。
Output
每组测试实例，若挑战者能走出迷宫输出”YES”，否则输出“NO”。
Sample Input
3 3
#*#
#*#
#*#
3 3
#*#
###
#*#
Sample Output
YES
NO
AC代码：
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std; char str[][];
bool flag[][];
int dri[][]= {{-,},{,},{,-},{,}};
struct Door
{
int x,y;
} door[]; int bfs(int n,int m)
{
memset(flag,false,sizeof(flag));
queue<Door>q;
Door now,next;
q.push(door[]);
flag[door[].x][door[].y]=true;
while(!q.empty())
{
now=q.front();
q.pop();
if(now.x==door[].x && now.y==door[].y) return ;
for(int i=; i<; i++)
{
next.x=now.x+dri[i][];
next.y=now.y+dri[i][];
if(next.x>=&&next.x<n && next.y>=&&next.y<m && next.x==door[].x && next.y==door[].y) return ;
else if(next.x>=&&next.x<n && next.y>=&&next.y<m && !flag[next.x][next.y] && str[next.x][next.y]=='*')
{
q.push(next);
flag[next.x][next.y]=true;
}
}
}
return -;
} int main()
{
int n,m,i;
while(scanf("%d%d",&n,&m)==)
{
getchar();
for(i=; i<n; i++)
scanf("%s",str[i]);
int num=;
for(i=; i<m; i++)
{
if(str[][i]=='*')
{
door[num].x=;
door[num].y=i;
num++;
}
if(str[n-][i]=='*')
{
door[num].x=n-;
door[num].y=i;
num++;
}
}
for(i=; i<n-; i++)
{
if(str[i][]=='*')
{
door[num].x=i;
door[num].y=;
num++;
}
if(str[i][m-]=='*')
{
door[num].x=i;
door[num].y=m-;
num++;
}
}
int ans=bfs(n,m);
if(ans==) printf("YES\n");
if(ans==-) printf("NO\n");
}
return ;
}