迷宫问题（dfs）

问题 1672: 迷宫问题

时间限制: 1Sec 内存限制: 32MB

题目描述
小明置身于一个迷宫，请你帮小明找出从起点到终点有多少种走法。
小明只能向上下左右四个方向移动。
输入
输入包含多组测试数据。输入的第一行是一个整数T，表示有T组测试数据。
每组输入的第一行是两个整数N和M（1<=N,M<=100）。
接下来N行，每行输入M个字符，每个字符表示迷宫中的一个小方格。
字符的含义如下：
‘s’：起点
‘e’：终点
‘-.：空地，可以通过
‘#’：障碍，无法通过
输入数据保证有且仅有一个起点和终点。
输出
对于每组输入，输出多少中走法，如果不存在从起点到终点的路，则输出-1。
样例输入：

样例输出：
1
分析：利用深搜统计即可

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
int m,n;
int ans=0;//记录次数 
bool vis[1005][1005];
int dir[4][2]{{-1,0},{0,-1},{1,0},{0,1}};
string mp[1005];
bool in(int x,int y){
	return x>=0&&x<m&&y>=0&&y<n;
}
void dfs(int x,int y){
	if(mp[x][y]=='e'){
		ans++;
		return;
	}
	vis[x][y]=true;
	for(int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if(in(tx,ty)&&!vis[tx][ty]&&mp[tx][ty]!='#'){
			dfs(tx,ty);
		}
	}
	vis[x][y]=false;
} 
int main(){
	cin>>m>>n;
	int x,y;
	for(int i=0;i<m;i++){
		cin>>mp[i];
	}
	for(int i=0;i<m;i++){//找到起点 
		for(int j=0;j<n;j++){
			if(mp[i][j]=='s'){
				 x=i;
				 y=j;
			}
		}
	}
	dfs(x,y);
	if(ans>0)
	cout<<ans<<endl;
	else
	printf("-1");
	return 0;
} 

运行结果：