LC.P1034[边界着色]

方法一：BFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.length, n = grid[0].length;
        int[][] ans = new int[m][n];
        int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        Deque<int[]> queue = new ArrayDeque<>();
        queue.offer(new int[]{row, col});
        while (!queue.isEmpty()) {
            int[] cur = queue.poll();
            int x = cur[0], y = cur[1], cnt = 0;
            for (int[] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue; // 越界
                if (grid[x][y] != grid[nx][ny]) continue; // 不是同一个连通分量
                else ++cnt;
                if (ans[x][y] == 0) queue.offer(new int[]{nx, ny}); // 若[x, y]未被处理过，则加入队列
            }
            ans[x][y] = cnt == 4 ? grid[x][y] : color; // 若不是边界，则为原grid[x][y]值，否则涂成color
        }
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (ans[i][j] == 0) ans[i][j] = grid[i][j];
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(m × n)$
  • 空间复杂度：$O(m × n)$

方法二：DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
    int m, n, color;
    int[][] grid, ans;
    int[][] dirs = new int[][]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        this.grid = grid;
        this.color = color;
        m = grid.length;
        n = grid[0].length;
        ans = new int[m][n];
        dfs(row, col);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (ans[i][j] == 0) ans[i][j] = grid[i][j];
            }
        }
        return ans;
    }

    private void dfs(int x, int y) {
        int cnt = 0;
        for (int[] dir : dirs) {
            int nx = x + dir[0], ny = y + dir[1];
            if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
            if (grid[x][y] != grid[nx][ny]) continue;
            else ++cnt;
            if (ans[nx][ny] != 0) continue;
            ans[nx][ny] = -1; // 标记为使用过
            dfs(nx, ny);
        }
        ans[x][y] = cnt == 4 ? grid[x][y] : color;
    }
}
  • 时间复杂度：$O(m × n)$
  • 空间复杂度：$O(m × n)$