題意

給出一個無向圖和終點的編號
按字典序枚舉出從1到終點的路徑

思路

要事先判斷結點1是否可以到達結點k, 用一個bool judge()函數判斷一下從終點能否回到1點即可. 如果無解直接輸出有0種走法
有解則用dfs即可. 因為每種走法里一個編號只能走一次, 用一個數組m[]標記是否走過. 記得每次標記之后進入dfs(), 出來之后要清除該標記, 以防影響程序后面的判斷
DFS在回溯時要取消原先的標記
而BFS不存在回溯也就不存在取消標記這一問題。

話說這道題的格式, 是沒有前導空格的
VJ給的PDF顯示有點問題 =_=

AC代碼

#include <iostream> #include <algorithm> #include <cstdio> #include <cstring>using namespace std;#define mst(a) memset(a,0,sizeof(a)); const int maxn = 30; int G[maxn][maxn], vis[maxn][maxn], m[maxn], r[maxn]; int aim, mmax, all;bool judge(int n) {if( n == 1 ) return true;m[n] = 1;for( int i = mmax; i >= 1; i-- ){if( m[i] ) continue;if( G[n][i] )if( judge(i) )return true;}return false; }void print( int len ) {all++;printf("1");for( int i = 0; i < len; i++ )printf(" %d",r[i]);puts(""); }void dfs( int n, int k ) {if( n == aim )print(k);for( int i = 2; i <= mmax; i++ ){if( !m[i] && G[n][i] ){m[i] = 1;r[k] = i;dfs(i, k+1);m[i] = 0;}} }void solve() {mst(m);dfs(1, 0); }int main() {int a, b, kase = 0;while( ~scanf("%d",&aim) ){mmax = aim, all = 0;mst(G);mst(vis);mst(m);mst(r);while( scanf("%d%d",&a,&b) == 2 && a ){G[a][b] = 1;G[b][a] = 1; //雙向可走mmax = max(mmax,a);mmax = max(mmax,b);}printf("CASE %d:\n",++kase);if(!judge(aim)){printf("There are 0 routes from the firestation to streetcorner %d.\n",aim);continue;}solve();printf("There are %d routes from the firestation to streetcorner %d.\n",all, aim);}return 0; }

轉載于:https://www.cnblogs.com/JinxiSui/p/9740591.html

總結

以上是生活随笔為你收集整理的UVa 208 - Firetruck (回溯)的全部內容，希望文章能夠幫你解決所遇到的問題。

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