130. 被围绕的区域

给你一个 m x n 的矩阵 board ,由若干字符 'X' 和 'O' ,找到所有被 'X' 围绕的区域,并将这些区域里所有的 'O' 用 'X' 填充。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


官方题解从边界向内扩展更简单

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

class Solution {

    private int[] dx = {0, 1, 0, -1};

    private int[] dy = {1, 0, -1, 0};

    public void solve(char[][] board) {
        if (board == null || board.length == 0 || board[0].length == 0) {
            return;
        }
        Map<Character, Boolean> ok = new HashMap<>();

        int n = board.length, m = board[0].length;

        char idx = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (board[i][j] == 'O') {
                    idx++;
                    LinkedList<int[]> queue = new LinkedList<>();
                    queue.offer(new int[]{i, j});
                    board[i][j] = idx;
                    boolean isOk = true;

                    while (!queue.isEmpty()) {
                        int[] node = queue.poll();

                        for (int k = 0; k < 4; ++k) {
                            int x = dx[k] + node[0];
                            int y = dy[k] + node[1];
                            if (x < 0 || x >= n || y < 0 || y >= m) {
                                isOk = false;
                            } else if (board[x][y] == 'O') {
                                queue.offer(new int[]{x, y});
                                board[x][y] = idx;
                            }
                        }
                    }
                    ok.put(idx, isOk);
                }
            }
        }

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (ok.containsKey(board[i][j])) {
                    if (ok.get(board[i][j])) {
                        board[i][j] = 'X';
                    } else {
                        board[i][j] = 'O';
                    }
                }
            }
        }
    }
}
上一篇:iTOP-4412开发板资料更新速报


下一篇:学习4412开发板+项目实战+配套视频+每日指导