LeetCode 130 Surrounded Regions

Tag: 深度优先搜索 LeetCode Posted on 2022-02-09 00:16:19 Edited on 2022-02-09 14:44:17 Views: 164

概述

https://leetcode.com/problems/surrounded-regions/

直接法

每个元素如果四周都是 X 或者是 W,就将其设置为 X。W 意味着该元素的是否可以翻转正待确认。

以下是一个通过了 37/58 测试样例的错误解法:

class Solution {
public:
    
    void solve(vector<vector<char>>& board) {
        for (int i = 0; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                helper(board, i, j);
            }
        }
    }
    
    bool helper(vector<vector<char>>& board, int i, int j) {
        if (i == -1 || j == -1 || i == board.size() || j == board[0].size()) return false;
        if (board[i][j] == 'X') return true;
        if (board[i][j] == 'W') return true;
        board[i][j] = 'W';
        if (helper(board, i + 1, j) && helper(board, i - 1, j) && helper(board, i , j + 1) && helper(board, i, j - 1)) {
            board[i][j] = 'X';
            return true;
        }
        board[i][j] = 'O';
        return false;
    }
};

输入:

[["O","X","X","O","X"],
 ["X","O","O","X","O"],
 ["X","O","X","O","X"],
 ["O","X","O","O","O"],
 ["X","X","O","X","O"]]

输出(A 是被错误翻转的地方):

[["O","X","X","O","X"],
 ["X","X","X","X","O"],
 ["X","X","X","A","X"],
 ["O","X","O","O","O"],
 ["X","X","O","X","O"]]

我还是没想通为啥这个地方会搞错,可以看到其下面的区域是没有搞错的,唯一的解释是, 其下面的区域之前也被搞错了,但是后来被纠正了过来,但是想要被纠正,其就不能是 X 和 W, 所以当时只能是 O,这就意味着其没被搞错,矛盾了啊!所以其下面的全程没被搞错, 但是这样的话其又是怎么导致该各被设置为 X 嘞?代码中只有一个地方可以设置其为 X, 只能上下左右全为 true 啊。

深度优先搜索

遍历四周的点,标记所有与四周相连的 O 为 #,这之后剩下的 O 就是要翻转的 O。 时间复杂度 O(mn),因为每个元素只被处理一次。

class Solution {
public:
    
    void solve(vector<vector<char>>& board) {
        for (int i = 0; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                if (i == 0 || j == 0 || i == board.size() - 1 || j == board[0].size() - 1) dfs(board, i, j);
            }
        }
        for (int i = 0; i < board.size(); i ++) {
            for (int j = 0; j < board[0].size(); j ++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                } else {
                    board[i][j] = 'X';
                }
            }
        }
    }
    
    void dfs(vector<vector<char>>& board, int i, int j) {
        if (i == -1 || j == -1 || i == board.size() || j == board[0].size()) return;
        if (board[i][j] == 'O') {
            board[i][j] = '#';
            dfs(board, i + 1, j);
            dfs(board, i - 1, j);
            dfs(board, i, j + 1);
            dfs(board, i, j - 1);
        }
    }
};

并查集解法

我看了下,有点麻烦,大致思想是设置一个 dummy 节点,然后遍历四周的 O,设置其与 dummy 连通, 然后遍历棋盘中剩余部分,对其中的 O,设置其与四周的 O 连通。

最后再遍历一遍棋盘,翻转那些不与 dummy 连通的节点就好了。

https://labuladong.gitee.io/algo/2/19/39/

未经允许,禁止转载,本文源站链接:https://iamazing.cn/