迷宮

題目背景

給定一個N*M方格的迷宮，迷宮里有T處障礙，障礙處不可通過。給定起點坐標和終點坐標，問: 每個方格最多經(jīng)過1次，有多少種從起點坐標到終點坐標的方案。在迷宮中移動有上下左右四種方式，每次只能移動一個方格。數(shù)據(jù)保證起點上沒有障礙。

題目描述

輸入格式：

第一行N、M和T，N為行，M為列，T為障礙總數(shù)。第二行起點坐標SX,SY，終點坐標FX,FY。接下來T行，每行為障礙點的坐標。

輸出格式：

給定起點坐標和終點坐標，問每個方格最多經(jīng)過1次，從起點坐標到終點坐標的方案總數(shù)。

輸入輸出樣例

輸入樣例#1

2 2 1 1 1 2 2 1 2

輸出樣例#1

1

說明

【數(shù)據(jù)規(guī)模】
1≤N,M≤5

AC代碼

#include<bits/stdc++.h> using namespace std; int q[101][101]; long long sum=0; int i,j,n,m,t,sx,sy,x,y,ex,ey; void dfs(int a,int b) {if (a==ex&&b==ey)//如果找到了終點 {sum++;//方案數(shù) + 1 return;}else{q[a][b]=0;//把當前節(jié)點置為已選擇 if (q[a - 1][b] != 0){dfs(a - 1,b);q[a - 1][b] = 1;}if (q[a + 1][b] != 0){dfs(a + 1,b);q[a + 1][b] = 1;}if (q[a][b - 1] != 0){dfs(a,b - 1);q[a][b - 1] = 1;}if (q[a][b + 1] != 0){dfs(a,b + 1);q[a][b + 1] = 1;}//以當前節(jié)點為中心向四個方向無限拓展,直到找不到鄰節(jié)點或碰到障礙物 } } int main() {memset(q,0,sizeof(q));//初始化棋盤所有節(jié)點為不可用 cin>>n>>m>>t;//n是行 m是列 t是障礙物的個數(shù) cin>>sx>>sy>>ex>>ey;// sx sy是起點的坐標 ex ey是終點的坐標 for(i=1;i<=n;i++)for(j=1;j<=m;j++)q[i][j]=1;//找到迷宮中所有可走的節(jié)點 for(i=1;i<=t;i++){cin>>x>>y;q[x][y]=0;//把障礙物標為不可用 }dfs(sx,sy);//把起點作為入?yún)⑦M行DFS cout<<sum<<endl;//sum是方案總數(shù) return 0; }

思路總結

step1:先寫return的條件
step2:把當前所在的節(jié)點設為不可用
step3:搜索4個方向可用的節(jié)點
step4:切換到最先找到的節(jié)點,選中,重復step2,step3,step4

轉載于:https://www.cnblogs.com/LJA001162/p/11220935.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結

以上是生活随笔為你收集整理的c++ 深度优先搜索(迷宫)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。