題目背景（題目鏈接）
題目描述
給定一個N*M方格的迷宮，迷宮里有T處障礙，障礙處不可通過，
在迷宮中移動有上下左右四種方式，每次只能移動一個方格，資料保證起點上沒有障礙，
給定起點坐標和終點坐標，每個方格最多經過一次，問有多少種從起點坐標到終點坐標的方案，
輸入格式
第一行為三個正整數 N,M,T，分別表示迷宮的長寬和障礙總數，
第二行為四個正整數 SX,SY,FX,FY，SX,SY代表起點坐標，FX,FY代表終點坐標，
接下來 $T$ 行，每行兩個正整數，表示障礙點的坐標，
輸出格式
輸出從起點坐標到終點坐標的方案總數，
樣例輸入 樣例輸出
2 2 1 1
1 1 2 2
1 2
題解
解題思路
經典的DFS+回溯題目，從起點向四周遞回搜索，遇到邊界，障礙或走過的路就回溯一步改變方向繼續搜索，統計最終到達終點的次數（幾道類似的題目：P1141，P1238），詳細思路見代碼，
1 #include<bits/stdc++.h>//萬能頭檔案 2 using namespace std; 3 int a,b,c,d; 4 int ans; 5 int z[101][101]; 6 int zx,zy; 7 int n,m,t; 8 void dfs(int p,int q) 9 { 10 if(p==c&&q==d) 11 { 12 ans++; 13 return; 14 }//如果到達終點，就回到上一層 15 z[p][q]=0; 16 if(z[p][q+1]!=0) 17 { 18 dfs(p,q+1); 19 z[p][q+1]=1; 20 }//如果右邊可以走，就走 21 if(z[p][q-1]!=0) 22 { 23 dfs(p,q-1); 24 z[p][q-1]=1; 25 }//走左邊 26 if(z[p-1][q]!=0) 27 { 28 dfs(p-1,q); 29 z[p-1][q]=1; 30 }//走上邊 31 if(z[p+1][q]!=0) 32 { 33 dfs(p+1,q); 34 z[p+1][q]=1; 35 }//走下邊 36 } 37 int main() 38 { 39 memset(z,0,sizeof(z));//將z陣列全部賦值為0 40 41 cin>>n>>m>>t;//輸入迷宮的長、寬以及障礙的數量 42 cin>>a>>b>>c>>d;//(a,b)為起點坐標，(c,d)為終點坐標 43 44 for(int i=1;i<=n;i++) 45 for(int j=1;j<=m;j++) 46 z[i][j]=1;//將迷宮區域全部賦值1，代表可以走 47 for(int i=1;i<=t;i++) 48 { 49 cin>>zx>>zy;//輸入障礙的坐標 50 z[zx][zy]=0;//將障礙的坐標賦值為0，代表不可以走 51 } 52 dfs(a,b);//進行深搜 53 cout<<ans<<endl;輸出路的數量 54 return 0;//完結撒花 55 }//提交記錄
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/542687.html
標籤：其他