題目背景

迷宮 【問題描述】

給定一個N*M方格的迷宮，迷宮里有T處障礙，障礙處不可通過。給定起點坐標和

終點坐標，問: 每個方格最多經過1次，有多少種從起點坐標到終點坐標的方案。在迷宮

中移動有上下左右四種方式，每次只能移動一個方格。數據保證起點上沒有障礙。

輸入樣例 輸出樣例

【數據規模】

1≤N,M≤5

題目描述

輸入輸出格式

輸入格式：

?

【輸入】

第一行N、M和T，N為行，M為列，T為障礙總數。第二行起點坐標SX,SY，終點

坐標FX,FY。接下來T行，每行為障礙點的坐標。

?

輸出格式：

?

【輸出】

給定起點坐標和終點坐標，問每個方格最多經過1次，從起點坐標到終點坐標的方

案總數。

?

輸入輸出樣例

輸入樣例#1：?復制 2 2 1 1 1 2 2 1 2 輸出樣例#1：?復制 1


一開始想的是廣搜 每個node里面有個vis 但是這種方法吃力不討好
直接回溯法即可 解決了vis重疊的問題
有一個要注意的是 起點要設置vis=1 不然有一些點沒法過 #include<bits/stdc++.h> using namespace std; //input by bxd #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i>=(b);i--) #define RI(n) scanf("%d",&(n)) #define RII(n,m) scanf("%d%d",&n,&m) #define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k) #define RS(s) scanf("%s",s); #define LL long long #define pb push_back #define fi first #define REP(i,N) for(int i=0;i<(N);i++) #define CLR(A,v) memset(A,v,sizeof A) /// #define inf 0x3f3f3f3f #define N 100 int n,m; int mp[N][N]; int vis[N][N]; int sx,sy,ex,ey; int cnt=0; int dx[4]={0,0,-1,1}; int dy[4]={1,-1,0,0};void dfs(int x,int y) {if(x==ex&&y==ey){cnt++;return ;}rep(i,0,3){int a=x+dx[i];int b=y+dy[i];if(mp[a][b]==0)continue;if(vis[a][b])continue;vis[a][b]=1;dfs(a,b);vis[a][b]=0;} } int main() {int t;RIII(n,m,t);rep(i,1,n)rep(j,1,n)mp[i][j]=1;RIII(sx,sy,ex);RI(ey);rep(i,1,t){int a,b;RII(a,b);mp[a][b]=0;}vis[sx][sy]=1;dfs(sx,sy);cout<<cnt;return 0; } View Code

?

轉載于:https://www.cnblogs.com/bxd123/p/10614403.html

總結

以上是生活随笔為你收集整理的P1605 迷宫 dfs回溯法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。