度優先搜索（DFS）是一個遞歸過程，有回退過程。

下面是一道OJ上的題目，借此來實現下DFS~

題目來源：

Zhejiang Provincial Programming Contest 2004,ZOJ2110

題目描述：

一只小狗在一個古老的迷宮里找到一根骨頭，當它叼起骨頭時，迷宮開始顫抖，它感覺到地
面開始下沉。它才明白骨頭是一個陷阱，它拼命地試著逃出迷宮。
迷宮是一個N×M 大小的長方形，迷宮有一個門。剛開始門是關著的，并且這個門會在第T 秒
鐘開啟，門只會開啟很短的時間（少于一秒），因此小狗必須恰好在第T 秒達到門的位置。每秒鐘，
它可以向上、下、左或右移動一步到相鄰的方格中。但一旦它移動到相鄰的方格，這個方格開始
下沉，而且會在下一秒消失。所以，它不能在一個方格中停留超過一秒，也不能回到經過的方格。
小狗能成功逃離嗎？請你幫助他。
輸入描述：
輸入文件包括多個測試數據。每個測試數據的第一行為三個整數：N M T，（1<N, M<7；
0<T<50），分別代表迷宮的長和寬，以及迷宮的門會在第T 秒時刻開啟。
接下來N 行信息給出了迷宮的格局，每行有M 個字符，這些字符可能為如下值之一：
X: 墻壁，小狗不能進入 S: 小狗所處的位置
D: 迷宮的門 . : 空的方格
輸入數據以三個0 表示輸入數據結束。
輸出描述：

對每個測試數據，如果小狗能成功逃離，則輸出"YES"，否則輸出"NO"。

樣例輸入：

3 4 5

S...

.X.X

...D

4 4 8

.X.X

..S.

....

DX.X

4 4 5

S.X.

..X.

..XD

....

0 0 0

樣例輸出：

YES

YES

NO

下面貼上代碼+注釋~

Code：

[cpp]?view plaincopyprint?

#include<iostream>??

#include<cmath>??

using?namespace?std;??

??

char?map[9][9];?//地圖??

int?n,?m,?t;????//迷宮的大小及門開啟的時間??

int?dir[4][2]?=?{?{0,?-1},?{0,?1},?{-1,?0},?{1,?0}?};???//4個方向??

bool?escape;????//記錄是否逃脫標志??

??

void?dfs(int?si,?int?sj,?int?di,?int?dj,?int?cnt)???//cnt為所用時間??

{??

????if(si>n?||?sj>m?||?si<=0?||?sj<=0)?return;??//越界??

????if(si?==?di?&&?sj?==?dj?&&?cnt?==?t)????????//臨界條件，在t時刻時走到出口~??

????{??

????????escape?=?1;??

????????return;??

????}??

????//剪枝（temp不能小于0且不能為奇數）??

????int?temp?=?t-cnt?-?abs(si-di)?-?abs(sj-dj);??

????if(temp<0?||?temp%2)?return;??

????//DFS遍歷??

????for(int?i?=?0;?i?<?4;?i++)?if(map[si+dir[i][0]][sj+dir[i][1]]?!=?'X')??

????{??

????????map[si+dir[i][0]][sj+dir[i][1]]?=?'X';??????//將走過的地方設為墻壁??

????????dfs(si+dir[i][0],?sj+dir[i][1],?di,?dj,?cnt+1);??

????????if(escape)?return;??????????????//當找到出口時，返回即可??

????????map[si+dir[i][0]][sj+dir[i][1]]?=?'.';??????//回退，恢復為可走點??

????}??

????return;??

}??

??

int?main()??

{??

????int?si,?sj;?????//小狗所在位置??

????int?di,?dj;?????//出口所在位置??

????while(scanf("%d%d%d",?&n,?&m,?&t))??//輸入迷宮的長n、寬m、及出口處門開的時刻t??

????{??

????????int?wall?=?0;???//墻壁的數量，便于剪枝??

????????getchar();??//屏蔽scanf后的轉行符的影響??

????????if(n?==?0?&&?m?==?0?&&?t?==?0)?break;???//當輸入"0?0?0"時結束??

????????//確定小狗坐標、出口坐標、墻壁的數量??

????????for(int?i?=?1;?i?<=?n;?i++)??

????????{??

????????????for(int?j?=?1;?j?<=?m;?j++)??

????????????{??

????????????????scanf("%c",?&map[i][j]);??

????????????????if(map[i][j]?==?'S')?{?si?=?i;?sj?=?j;?}??

????????????????else?if(map[i][j]?==?'D')?{?di?=?i;?dj?=?j;?}??

????????????????else?if(map[i][j]?==?'X')?wall++;??

????????????}??

????????????getchar();??//作用同上??

????????}?????

??????????

????????if(n*m?<=?t+wall)?{?printf("NO\n");?continue;?}??//剪枝??

??

????????escape?=?0;??

????????map[si][sj]?=?'X';??

??????

????????dfs(si,?sj,?di,?dj,?0);??

??????

????????if(escape)?printf("YES\n");???????

????????else?printf("NO\n");??

????}??

????return?0;??

}??

運行結果：

Ps：如有bug，歡迎拍磚~

總結

以上是生活随笔為你收集整理的实现DFS之“骨头的诱惑”的全部內容，希望文章能夠幫你解決所遇到的問題。

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