【問題描述】

湯姆有一塊好田，它是一個n×m方格的矩形，某些方格里面有一些大石頭。湯姆有一臺播種機。開始的時候，機器位于田地的左上角。機器播種完一個方格后，湯姆就把它開到一個相鄰的方格里，繼續(xù)播種。為了保護(hù)機器，湯姆不會把機器開到有石頭的方格里面，也不會開到剛剛播種過的方格里面。 湯姆希望在沒有石頭的方格里面都能播種，這可能嗎？

輸入

每個測試?yán)牡谝恍邪瑑蓚€整數(shù)n和m，表示田地的大小。 接下來n行描述田地，每行包含m個字符：‘S’表示方格里面有石頭，‘.’表示方格里面沒有石頭。

輸出

對每個測試?yán)?#xff0c;如果湯姆播種完畢，輸出“YES”，否則輸出“NO”。

輸入樣例	4?4 .S.. .S.. .... ....	4?4 .... ...S .... ...S	0?0
輸出樣例	YES	NO

【算法分析】

（1）數(shù)據(jù)結(jié)構(gòu)

//播種問題的數(shù)據(jù)結(jié)構(gòu) #define NUM 10 char field[NUM][NUM]; //田地 int n, m; //田地的大小 int visited; //訪問田地中方格的數(shù)量 int flag; //全部播種完畢的標(biāo)志 int count; //遞歸的次數(shù)計數(shù)

(2)判斷播種機能否播種完全部農(nóng)田的深度優(yōu)先搜索算法

void dfs(int x,int y) //形參是方格的坐標(biāo)（x,y） {if ( x<0 || y<0 || x>=n || y>=m) return;if (field[x][y]=='S') return;if (flag) return; 　//已經(jīng)全部播種完畢//遞歸的次數(shù)計數(shù)，限制不要超過1500次count ++;if (count>1500) return;//將方格里面置為石頭，避免重復(fù)搜索field[x][y] = 'S';visited ++;　//訪問的方格計數(shù)if (visited == n*m) 　//全部方格訪問完畢{flag = 1;return;}//分別向4個鄰近方格播種dfs(x+1, y);dfs(x-1, y);dfs(x, y+1);dfs(x, y-1);visited --;　//恢復(fù)遞歸現(xiàn)場field[x][y] = '.'; }

①是不是要等到所有遞歸都結(jié)束時，才知道播種機能否播種所有的可播種方格呢？測試表明，當(dāng)遞歸的次數(shù)達(dá)到1500時，標(biāo)志flag基本上已經(jīng)明確。

②限制visited＜1500（經(jīng)在線測試摸索），就可以限制很多不必要的搜索，在線測試時間降到0ms，否則是120ms。

//變量visited表示訪問田地中方格的數(shù)量，初始時visited是田地中有石頭方格的數(shù)量visited=0; for(int i=0;i<n;i++)for(int j=0;j<m;j++)if(field[i][j]=='S') visited++;

【代碼的完整實現(xiàn)】

#include<iostream>#define NUM 10 char field[NUM][NUM]; //田地 int n,m; //田地大小 int visited; //訪問田地中方格的數(shù)量 int flag; //全部播種完畢的標(biāo)志 int count; //遞歸次數(shù)統(tǒng)計 void dfs(int x,int y) //坐標(biāo) {if ( x<0 || y<0 || x>=n || y>=m) return;if (field[x][y]=='S') return;//已經(jīng)全部播種完畢//遞歸的次數(shù)計數(shù)，限制不要超過1500次if (flag) return;count ++;if (count>1500) return;//將方格里面置為石頭，避免重復(fù)搜索field[x][y] = 'S';visited ++; //訪問方格計數(shù) if (visited == n*m) //全部方格訪問完畢 {flag = 1;return;}//分別向4個鄰近方格播種dfs(x+1,y);dfs(x-1,y);dfs(x,y+1);dfs(x,y-1);visited --; //恢復(fù)遞歸狀態(tài) field[x][y] = '.'; }int main() {while (scanf("%d%d",&n,&m) && n && m) //輸入田地大小 {int i, j;for (i=0; i<n; i++)scanf("%s", field[i]); //輸入方格里面是否為石頭 visited = 0;for (i = 0; i<n ; i++)for (j = 0; j<m; j++)if (field[i][j]=='S') visited ++; //有石頭則訪問+1 flag = 0; //初始化 count = 0;dfs(0,0); //從（0,0）處開始遞歸處理 if (flag) printf("YES\n");else printf("NO\n");} return 0; }

總結(jié)

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

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