洛谷 P1605 迷宫

一道简单的dfs。

思路

输入n和m，用一个二维数组生成一个bool类型的图（省空间），还有t个障碍，for循环t次输入障碍坐标直接把数组[x][y]改为零就把图生成好了。

dfs如下：

int dfs(int x,int y){
	if (x==Tx-1&&y==Ty-1){
		return 1;
	}
	long long sum=0;
	vis[x][y]=1;
	for (int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if (in(tx,ty)&&mp[tx][ty]!=1&&!vis[tx][ty]){
			sum+=dfs(tx,ty);
		}
	}
	vis[x][y]=0;
	return sum;
}

最后，完整代码如下：

#include <bits/stdc++.h>
using namespace std;
int n,m,Tx,Ty,Sx,Sy;
int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};//扩展的4个方向
int mp[10][10];//地图
bool in(int x,int y){
	return 0<=x&&x<n&&y>=0&&y<m;
}//判断边界
int vis[10][10];
int dfs(int x,int y){
	if (x==Tx-1&&y==Ty-1){
		return 1;
	}
	long long sum=0;
	vis[x][y]=1;
	for (int i=0;i<4;i++){
		int tx=x+dir[i][0];
		int ty=y+dir[i][1];
		if (in(tx,ty)&&mp[tx][ty]!=1&&!vis[tx][ty]){
			sum+=dfs(tx,ty);
		}
	}
	vis[x][y]=0;
	return sum;
}//暴力dfs
int main(){
	int t;
	cin >>n>>m>>t;
	cin>>Sx>>Sy>>Tx>>Ty;
	for (int i=0;i<t;i++){
		int sbx,sby;
		cin>>sbx>>sby;
		mp[sbx-1][sby-1]=1;
	}//生成图
	cout << dfs(Sx-1,Sy-1);//输出
	return 0;
}

END