Leet Code題解 —— 1559. Detect Cycles in 2D Grid 檢測二維無向圖中的環

• 前言
• 一、題目描述
• 二、思路整理
• • 1. 審題
  • 2. 分布實現步驟
  • • 2.1 將二維數組處理為連通圖
    • 2.2 判斷連通圖中是否有環
• 三、實現樣例

---

前言

找找感覺，記錄一下個人解題思路系列。記錄一下力扣里面的經典題目的個人想法。

---

一、題目描述

https://leetcode.com/problems/detect-cycles-in-2d-grid/
在二維無向圖中檢測環。如果有多個環，只要判斷任意一個。

給定一個m*n的二維字符數組，請找出該數組中，是否存在由相同值構成的環。
一個環應該是一個長度不少于4的路徑，該路徑的起點和終點都在同一格內。
對任意給定格子來說，我們只能移動到其相鄰格（僅限上、下、左、右四個方向，不包括斜角方向），同時，該相鄰格應具有同當前格相同的值。
同時，你不能移動到你上一次曾移動過的各自中，例如：(1, 1) -> (1, 2) -> (1,1)不屬于有效的環，因為對于(1, 2)來說，(1, 1)是上次訪問過的格。
若存在相同值構成的環，則返回true，否則返回false。

1. 例一

輸入: grid = [[“a”,“a”,“a”,“a”],[“a”,“b”,“b”,“a”],[“a”,“b”,“b”,“a”],[“a”,“a”,“a”,“a”]]
輸出: true
解釋: 如下圖，有兩個環。

2. 例二

輸入: grid = [[“c”,“c”,“c”,“a”],[“c”,“d”,“c”,“c”],[“c”,“c”,“e”,“c”],[“f”,“c”,“c”,“c”]]
輸出: true
解釋: 如下圖，有一個環。

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
格內僅包含小寫字母。

二、思路整理

1. 審題

可以看到，給的判斷函數的原型是：bool containsCycle(vector<vector>& grid) {}
其中，輸入的可以看做是一個二維的數組，數組內填充的是小寫字母。
輸出要求的只是判斷是否存在環的結果。
一般環的判斷，我們是基于聯通圖來做的。所以，這個二維的數組我們先需要把它轉為連通圖。那么整題的步驟分為：

將二維數組處理為連通圖

判斷連通圖中是否有環

2. 分布實現步驟

2.1 將二維數組處理為連通圖

由于原數組是二維數組，為了簡化我們的處理邏輯，我們可以將二維的圖處理為一維圖。
我們可以采用一維鏈表來存儲，并根據原圖內數據（字母）處理其連通性，若：
m == grid.length
n == grid[i].length
i, j為原二維數組下標
新一維數組下標 index = i * n + j;

如下圖，原表示為：
vector<vector> grid1 =
{

{'a','a','a','a'},{'a','b','b','a'},{'a','b','b','a'},{'a','a','a','a'}};

處理后的連通圖為
0 : 1, 4;
1 : 0, 2;
2 : 1, 3;
3 : 2, 7;
4 : 0, 8;
5 : 9, 6;
6 : 5, 10;
7 : 3, 11;
8 : 4, 12;
9 : 5, 10;
10 : 6, 9;
11 : 7, 15;
12 : 8, 13;
13 : 12, 14;
14 : 13, 15;
15 : 11, 14;

2.2 判斷連通圖中是否有環

得到連通圖后，本題即轉換為基于一個無向圖判斷有環的問題。
判斷圖中的環，我們可以采用 DFS，深度優先檢索來判斷是否有環。
深度優先的通常寫法是遞歸型的，即對現有的節點進行判斷，并遍歷其子節點，然后依次對子節點進行深度優先搜索。

遍歷上述連通圖，在遍歷的過程中，我們只需判斷某節點是否有一條邊指向已訪問過的節點，如果有，則表示存在環。但需注意：

• 判斷已訪問過的節點，不應該是當前節點的父節點（無向圖兩個節點間是互相可聯通的，但這種父子節點間的連通性不被認為是環）；
• 一個節點有三種狀態，因此我們的判斷應該是，遍歷過程中如果發現某節點存在一條邊指向非父節點的已被訪問的灰色節點，則存在環；
  • 已遍歷完全（該節點所有的路徑（或子節點）均已被遍歷） —— 黑色
  • 已被訪問但未遍歷完全 —— 灰色
  • 未被訪問 —— 白色
• 由于遍歷是遞歸的，因此在某一次的子遞歸函數中存在環，則需要向上傳遞該判定結果

三、實現樣例

class Solution { private:bool dfs(vector<vector<int>> &connected_graph, int &start_node){bool has_cycle = false;// flag the node has been visitedreached[start_node] = 1;for (auto child : connected_graph[start_node]) {if (reached[child] == 1 && child != parent_node[start_node]) {has_cycle = true;break;}else if (reached[child] == 0) {parent_node[child] = start_node;// pass the has_cycle result to upper layerhas_cycle = dfs(connected_graph, child);if (has_cycle == true){break;}}}// all the path is visitedreached[start_node] = 2;return has_cycle;}// represent the all the nodes can be reached to this nodevector<int> reached;vector<int> parent_node;public:bool containsCycle(vector<vector<char>>& grid) {vector<vector<int>> connected_graph;/******************************************//* Step 1. initialize the connected graph *//******************************************/connected_graph.resize(grid.size()*grid[0].size());reached.resize(grid.size()*grid[0].size());parent_node.resize(grid.size()*grid[0].size());for(auto var : parent_node){var = grid.size()*grid[0].size();}int i = 0; int j = 0;for(i=0; i<grid.size(); i++){for(j=0; j<grid[0].size(); j++){// calculator how many ways each block can accessif(i>0){if(grid[i][j] == grid[i-1][j]){connected_graph[i*grid[0].size()+j].push_back((i-1)*grid[0].size()+j);}}if(j>0){if(grid[i][j] == grid[i][j-1]){connected_graph[i*grid[0].size()+j].push_back(i*grid[0].size()+j-1);}}if(i<grid.size()-1){if(grid[i][j] == grid[i+1][j]){connected_graph[i*grid[0].size()+j].push_back((i+1)*grid[0].size()+j);}}if(j<grid[0].size()-1){if(grid[i][j] == grid[i][j+1]){connected_graph[i*grid[0].size()+j].push_back(i*grid[0].size()+j+1);}}}}/******************************************//* Step 2. judge there has cycle *//******************************************/bool has_cycle = false;for (int k = 0; k < reached.size(); k++){/* begin the dfs search beginning node */if(reached[k] == 0){// bfs search from node-khas_cycle = dfs(connected_graph, k);}else{continue;}if(has_cycle == true){return true;}}return has_cycle; } }; 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的Leet Code题解 - 1559. Detect Cycles in 2D Grid 检测二维无向图中的环的全部內容，希望文章能夠幫你解決所遇到的問題。

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