DFS解决走障碍物迷宫路径数问题
作者:
KM_7
,
2023-04-07 17:14:03
,
所有人可见
,
阅读 169
#include <iostream>
using namespace std;
const int N=1000;
int n,m,t;
int map[N][N];
bool vis[N][N];
int startx,starty,endx,endy;
int cnt;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
void dfs(int x,int y){
if(x==endx&&y==endy){
cnt++;
return;
}
for(int i=0;i<4;i++){
int tx=x+dx[i] , ty=y+dy[i];
if(tx<1||tx>n||ty<1||ty>m||vis[tx][ty]||map[tx][ty]) continue;
vis[tx][ty]=true;
dfs(tx,ty);
vis[tx][ty]=false;
}
}
int main(){
cin>>n>>m>>t;
cin>>startx>>starty>>endx>>endy;
while(t--){
int x, y;
cin>>x>>y;
map[x][y]=1;
}
dfs(startx,starty);
cout<<cnt<<endl;
return 0;
}