迷宫《1》

一天蒜头君掉进了一个迷宫里面，蒜头君想逃出去，可怜的蒜头君连迷宫是否有能逃出去的路都不知道。

看在蒜头君这么可怜的份上，就请聪明的你告诉蒜头君是否有可以逃出去的路。

输入格式

第一行输入两个整数 �n 和 �m，表示这是一个 �×�n×m 的迷宫。

接下来的输入一个 �n 行 �m 列的迷宫。其中 'S' 表示蒜头君的位置，'*'表示墙，蒜头君无法通过，'.'表示路，蒜头君可以通过'.'移动，'T'表示迷宫的出口（蒜头君每次只能移动到四个与他相邻的位置——上，下，左，右）。

输出格式

输出一个字符串，如果蒜头君可以逃出迷宫输出"yes"，否则输出"no"。

数据范围

1≤�,�≤101≤n,m≤10。

Sample 1

Inputcopy	Outputcopy
3 4 S**. ..*. ***T	no

Sample 2

Inputcopy	Outputcopy
3 4 S**. .... ***T	yes

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

using namespace std;

char a[20][20];

int v[20][20];

struct point{

int x;int y;

};

int dx[4]={0,1,0,-1};

int dy[4]={1,0,-1,0};

queue<point>q;

int main(){

int n,m;cin>>n>>m;

int qx,qy,zx,zy;

for(int i=1;i<=n;i++){

for(int j=1;j<=m;j++){

cin>>a[i][j];

if(a[i][j]=='S'){

qx=i;qy=j;//1 1

}

if(a[i][j]=='T'){

zx=i;zy=j;//3 4

}

}

}

point start;

start.x=qx;start.y=qy;//1 1

q.push(start);//1 1

v[qx][qy]=1;//v[1][1]=1

while(!q.empty()){

int x=q.front().x,y=q.front().y;//1 1

if(x==zx&&y==zy){//到达终点

cout<<"yes"<<endl;

return 0;

}

for(int i=0;i<4;i++){//四个方向

int tx,ty;//测试x，y

tx=x+dx[i];

ty=y+dy[i];

if(tx>0&&ty>0&&tx<=n&&ty<=m&&a[tx][ty]!='*'&&!v[tx][ty]){

point temp;

temp.x=tx;

temp.y=ty;

q.push(temp);

v[tx][ty]=1;

}

}

q.pop();

}

cout<<"no"<<endl;

return 0;

}