二維網(wǎng)格圖中探測環(huán)
給你一個二維字符網(wǎng)格數(shù)組 grid ，大小為 m x n ，你需要檢查 grid 中是否存在 相同值 形成的環(huán)。

一個環(huán)是一條開始和結(jié)束于同一個格子的長度 大于等于 4 的路徑。對于一個給定的格子，你可以移動到它上、下、左、右四個方向相鄰的格子之一，可以移動的前提是這兩個格子有 相同的值 。

同時，你也不能回到上一次移動時所在的格子。比方說，環(huán) (1, 1) -> (1, 2) -> (1, 1) 是不合法的，因為從 (1, 2) 移動到 (1, 1) 回到了上一次移動時的格子。

如果 grid 中有相同值形成的環(huán)，請你返回 true ，否則返回 false 。

示例 1：

輸入：grid = [[“a”,“a”,“a”,“a”],[“a”,“b”,“b”,“a”],[“a”,“b”,“b”,“a”],[“a”,“a”,“a”,“a”]]
輸出：true
解釋：如下圖所示，有 2 個用不同顏色標出來的環(huán)：

示例 2：

輸入：grid = [[“c”,“c”,“c”,“a”],[“c”,“d”,“c”,“c”],[“c”,“c”,“e”,“c”],[“f”,“c”,“c”,“c”]]
輸出：true
解釋：如下圖所示，只有高亮所示的一個合法環(huán)：

示例 3：

輸入：grid = [[“a”,“b”,“b”],[“b”,“z”,“b”],[“b”,“b”,“a”]]
輸出：false

提示：

m == grid.length
n == grid[i].length
1 <= m <= 500
1 <= n <= 500
grid 只包含小寫英文字母。

分析：看到題意就知道是個搜索題，但如何判斷環(huán)？這是解決本題的核心問題。
其實仔細想想，只要我下一個訪問的節(jié)點并不是上一個節(jié)點，并且和當前節(jié)點的字符相同，不就符合環(huán)的定義嗎？并不需要一定是一個完整的環(huán)，在搜索的半路找到了環(huán)就足以解題。 所以我們要記錄下上一個節(jié)點，不必判斷是否回到了起點。
保存上一個節(jié)點可以把行列下表都記錄下來，還有一個方法，就是把二維網(wǎng)格標號，那么每個位置的標號不就唯一了，唯一就可以判斷是否是上一個點，于是我們把x,y坐標轉(zhuǎn)化成一個唯一標號就可以判斷是否是上一個節(jié)點了。用唯一標識去判斷上一個點的好處是，減小了空間并能防止兩個點判斷相等時的錯誤，比如我要判斷這兩個點是否相等：x!=x’&&y!=y’對嗎？這里中間要用||才對，只要一個參數(shù)不同就是不同的點了，減小了犯邏輯錯誤的可能。這個題目還有一個陷阱，就是關(guān)于如何剪枝的問題，因為我們不可能對每一個節(jié)點都去搜索，這樣的搜索空間過于龐大，而搜索過的字符一定dfs都已經(jīng)搜索過，根據(jù)圖論，如果一個圖中存在環(huán)，無論無門從哪個位置走一定能找到一個環(huán)！所以這里我們盡可標記訪問過的點就好，連續(xù)的字符搜索一遍就夠了，不必恢復(fù)現(xiàn)場，因為要剪枝。搜索過程中我只要保證不繼續(xù)搜索上一個節(jié)點就可以了，訪問過的節(jié)點大可不必繞開走
本題剛開始想很好想，但容易落入深搜的陷阱，記錄一下。

class Solution { public:int book[510][510];int row,col,pre,dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};bool judge(int s,int e,int step,vector<vector<char>>& grid,int pre){if(book[s][e]&&step>3)return 1;book[s][e]=1;for(int i=0;i<4;i++){int ts = s+dir[i][0];int te = e+dir[i][1];if(te>=0&&ts>=0&&ts<row&&te<col&&grid[s][e]==grid[ts][te]&&pre!=ts*row+te){if(judge(ts,te,step+1,grid,s*row+e))return 1;}}return 0;}bool containsCycle(vector<vector<char>>& grid) {col = grid[0].size();row = grid.size();res=0;for(int i=0;i<row&&!res;i++){for(int j=0;j<col&&!res;j++){if(!book[i][j]&&judge(i,j,1,grid,-1))return 1;}}return 0;} };```

總結(jié)

以上是生活随笔為你收集整理的Leetcode 1559二维网格图中探测环 技巧DFS|剪枝的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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