https://leetcode.com/problems/coloring-a-border/
给定一个矩阵，里面有不同的数字，每个数字代表一种颜色。给定一个出发点，要求将其所在的连通块的边界都染成一个给定的颜色（这个给定的颜色不会是负数）。边界的定义是，或者在矩阵的边上，或者其四个方向的相邻格子有一个与自己颜色不同。
思路是floodfill，可以用DFS来解决。先将其边界全染色为 − 1 -1 −1，最后再将所有的 − 1 -1 −1都染色为给定的颜色。注意，这里不能一开始就直接把边界染色为给定的颜色，因为如果这样的话，遍历到一个位置的时候，即使它某个邻格与自己颜色不一样，也无法判断其是边界，还是因为那个邻格被染色了才不一样的。所以我们需要先将边界用一个特殊的数字标记。代码如下：
public class Solution { public int[][] colorBorder(int[][] grid, int r0, int c0, int color) { if (grid == null || grid.length == 0) { return grid; } // 记录某个格子是否访问过 boolean[][] visited = new boolean[grid.length][grid[0].length]; dfs(grid, visited, r0, c0, grid[r0][c0], new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}); for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == -1) { grid[i][j] = color; } } } return grid; } // 功能是对grid[x][y]所在的连通块的边界进行floodfill（即标记为-1） private void dfs(int[][] grid, boolean[][] visited, int x, int y, int originalColor, int[][] dirs) { // 标记当前格子为访问过 visited[x][y] = true; // 如果当前格子已经在grid边界上了，则直接标记为-1 if (x == 0 || x == grid.length - 1 || y == 0 || y == grid[0].length - 1) { grid[x][y] = -1; } // 接着继续尝试四个方向 for (int i = 0; i < 4; i++) { int X = x + dirs[i][0]; int Y = y + dirs[i][1]; // 如果在grid里，就进行下面的逻辑 if (inBound(grid, X, Y)) { // 如果grid[X][Y]在原图中颜色不是originalColor，说明grid[x][y]是边界，则标记为-1 if (checkColor(grid, X, Y, originalColor)) { grid[x][y] = -1; } // 如果grid[X][Y]未访问，并且颜色与originalColor一样，则访问并floodfill if (!visited[X][Y] && grid[X][Y] == originalColor) { dfs(grid, visited, X, Y, originalColor, dirs); } } } } // 判断是否在grid里 private boolean inBound(int[][] grid, int x, int y) { return 0 <= x && x < grid.length && 0 <= y && y < grid[0].length; } // 判断grid[x][y]与originalColor不同 // 注意，这里也需要判断grid[x][y]是否是-1， // 因为如果是-1，说明在原图中未标记之前，颜色也是originalColor private boolean checkColor(int[][] grid, int x, int y, int originalColor) { if (grid[x][y] != originalColor && grid[x][y] != -1) { return true; } else { return false; } }}时空复杂度 O ( n ) O(n) O(n)。