问题标题: 酷町堂：2147 危险的森林 超时10分

题目描述 Description

一个面积为n * n的森林，里面布满了陷阱，每个陷阱有2种状态：s和d。前者表示陷阱已经被破坏，后者表示陷阱正常。现在探险家伊泽处在森林中的某个位置，他每次只能移动到上、下、左、右这四个方向之一的相邻位置上，伊泽想要从点A走到点B，但是伊泽不能走出森林，请你写个程序，判断伊泽能不能办到。如果起点或者终点有一个布置有正常的陷阱(状态为d)，则看成无法办到。

输入描述 Input Description

第1行是测试数据的组数k。
每组测试数据的第一行数一个正整数n (1 <= n <= 100)，表示森林的面积是n * n的。
接下来输入n * n的矩阵，矩阵中的元素为s或者d。
再接下来一行是4个整数a, b,c, d，描述A处在第a行, 第b列，B处在第c行, 第d列。
注意：a,b,c,d都是从1开始计数的。

输出描述 Output Description

能办到则输出“YES”，否则输出“NO”。

样例输入 Sample Input

2
3
sdd
ssd
dss
1 1 2 2
5
sssss
dddsd
ssdss
dddss
sssds
1 1 4 1

样例输出 Sample Output

YES
NO

 

我的程序：

int n,sx,sy,fx,fy,dir[5][2]={{0},{1,0},{0,1},{-1,0},{0,-1}};
bool map[101][101],vis[101][101],cnt;
//深搜函数
void Dfs(int x,int y){
	if(x==fx&&y==fy){
		cnt=true;
		return;
	}
	for(int i=1;i<=4;i++){
		int nx=x+dir[i][0],ny=y+dir[i][1];
		if(!map[nx][ny]&&nx>=1&&nx<=n&&ny>=1&&ny<=n&&!vis[nx][ny]&&!cnt){
			vis[nx][ny]=true;
			Dfs(nx,ny);
			vis[nx][ny]=false;
		}
	}
}

//Main函数
char c;
int m;
cin>>m;
while(m--){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c;
			map[i][j]=(c=='d');
				vis[i][j]=false;
		}
	}
	cin>>sx>>sy>>fx>>fy;
	cnt=false;
	Dfs(sx,sy);
	if(cnt)cout<<"YES"<<endl;
	else 
	cout<<"NO"<<endl;
}

超时10分，测试点3正确

李翊冉在2019-11-20 12:50:00追加了内容

最后一个测试点Wrong Answer