題干：

福克斯在玩一款手機解迷游戲，這個游戲叫做”兩點”。基礎級別的時候是在一個n×m單元上玩的。像這樣：

?
?

每一個單元有包含一個有色點。我們將用不同的大寫字母來表示不同的顏色。

這個游戲的關鍵是要找出一個包含同一顏色的環。看上圖中4個藍點，形成了一個環。一般的，我們將一個序列?d1,d2,...,dk?看成一個環，當且僅當它符合下列條件時：

1.????這k個點不一樣，即當?i≠j時，?di?和?dj不同。

2.????k至少是4。

3.????所有的點是同一種顏色。

4.????對于所有的?1≤i≤k-1:?di?和?di+1?是相鄰的。還有?dk?和?d1?也應該相鄰。單元?x?和單元?y?是相鄰的當且僅當他們有公共邊。

當給出一幅格點時，請確定里面是否有環。

?

Input

單組測試數據。?
第一行包含兩個整數n和m (2≤n,m≤50):板子的行和列。?
接下來n行，每行包含一個有m個字母的串，表示當前行每一個點的顏色。每一個字母都是大寫字母。

Output

如果有環輸出Yes，否則輸出No。

Sample Input

3 4 AAAA ABCA AAAA 3 4 AAAA ABCA AADA

Sample Output

Yes No

解題報告：

? ?數據水啊，純暴力都能過。

? ?這題其實dfs中的狀態，加一個前驅的記錄，就不需要step了，這樣可以優化時間了。因為我們可以先跑并查集，然后一個集合一個集合的搜，如果搜到以前搜過的點，那就return 1;。

? ?這樣好處是，不需要一個一個點的搜索了，另外，這題vis數組是不需要回溯的。? ?

? ?另外，算是個dfs（換句話來說，是搜索的）的共同坑點吧，那就是對起點的標記，因為經常在起點那里就落下一個狀態，，，比如【51Nod - 1268】和為K的組合 （背包 或 dfs）這題。

AC代碼：

#include<bits/stdc++.h>using namespace std; int n,m; int nx[4] = {0,1,0,-1}; int ny[4] = {1,0,-1,0}; bool vis[55][55]; char maze[55][55]; bool ok(int x,int y) {if(x <= n && x >= 1 && y <= m && y >= 1) return 1;return 0; } bool dfs(int idx,int idy,char tar,int x,int y,int step) {if(x == idx && y == idy && step >=3 ) {return 1;}for(int k = 0; k<4; k++) {int tx = x+nx[k];int ty = y+ny[k];if(ok(tx,ty) && maze[tx][ty] == tar && vis[tx][ty] == 0) {vis[tx][ty]=1;if(dfs(idx,idy,tar,tx,ty,step+1)) return 1;}}return 0 ;} int main() {while(~scanf("%d%d",&n,&m)) {int flag = 0;memset(vis,0,sizeof vis);for(int i = 1; i<=n; i++) {scanf("%s",maze[i]+1);}for(int i = 1; i<=n; i++) {for(int j = 1; j<=m; j++) {for(int k = 0; k<4; k++) {if(maze[i+nx[k]][j+ny[k]] != maze[i][j]) continue;memset(vis,0,sizeof vis);vis[i+nx[k]][j+ny[k]]=1; // vis[i][j]=1;if(dfs(i,j,maze[i][j],i+nx[k],j+ny[k],0)) {flag=1;break;}}if(flag) break;}if(flag) break;}if(flag) puts("Yes");else puts("No");}return 0 ;}

總結：

? ? 剛開始還是犯了小錯誤，三層for那里，最外面兩層都寫的是<=n....其實內層應該是<=m

總結

以上是生活随笔為你收集整理的【51Nod - 1416】两点 （dfs 或 并查集+dfs）的全部內容，希望文章能夠幫你解決所遇到的問題。

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