链接：https://www.nowcoder.com/acm/contest/93/D
来源：牛客网

给你一个n*m的迷宫，这个迷宫中有以下几个标识：

s代表起点

t代表终点

x代表障碍物

.代表空地

现在你们涵哥想知道能不能从起点走到终点不碰到障碍物（只能上下左右进行移动，并且不能移动到已经移动过的点）。

输入描述:

输入第一行一个整数T(1<=T<=10)
接下来有T组测试数据，对于每一组测试数据，第一行输入2个数n和m(1<=n,m<=500)
接下来n行，每行m个字符代表这个迷宫，每个字符都是上面4个中的一种
数据保证只有一个起点和一个终点

输出描述:

对于每一组测试数据，如果可以的话输出YES，不可以的话输出NO

示例1
输入


1
3 5
s...x
x...x
...tx
输出

 

YES

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;
const int MAX=505;
int N,M;
char a[MAX][MAX];
int flag=0;
void dfs(int x,int y){
	if(a[x][y]=='t'){     //能够踩到“t”表示走出了迷宫
	   flag=1;            //标记flag为1
	   return;
	}
	      a[x][y]='x';     
	       int nx,ny;
	    for(nx=x-1,ny=y;nx<=x+1;nx+=2)
	    if(0<=nx&&nx<N&&0<=ny&&ny<M&&a[nx][ny]!='x')       //上下左右四方搜索
                         dfs(nx,ny);
            for(nx=x,ny=y-1;ny<=y+1;ny+=2)
            if(0<=nx&&nx<N&&0<=ny&&ny<M&&a[nx][ny]!='x')
                         dfs(nx,ny);								          
}
int main(){
	int p,q,t;
	scanf("%d",&t);
	while(t--){
        flag=0;
	scanf("%d%d",&N,&M);
	for(p=0;p<N;p++){
		for(q=0;q<M;q++){       
		cin>>a[p][q];
		}
	}
		for(int i=0;i<N;i++)
	{
		for(int j=0;j<M;j++)
		{
			if(a[i][j]=='s')    //从“s”开始搜
			{  
			   dfs(i,j);
			}
		}
	}
	if(flag){
		puts("YES");
	}
	if(!flag){
		puts("NO");
	}

	 }
	return 0;
}