题目解析

这道题最难的地方我觉得是题目意思不好理解- -,题目的意思的就是给你一个用数字代表颜色的地图,然后再给你一个坐标[row, col],把坐标所在格子连通的其他格子看成一整块(component),把这个整块的边界变为新的颜色。

方法

别问方法,问就是dfs。时间复杂度O(n),n是格子数。

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
35
36
37
38
39
40
41
class Solution {
public:
vector<vector<int>> colorBorder(vector<vector<int>>& grid, int r0, int c0, int color) {
vector<vector<bool>> visited(grid.size(), vector<bool>(grid[0].size(), false));
vector<vector<int>> new_grid = grid;
oc = grid[r0][c0];
helper(new_grid, grid, visited, r0, c0, color);
return new_grid;
}

void helper(vector<vector<int>> &grid, vector<vector<int>> &origin_grid, vector<vector<bool>> &visited, int row, int col, int color) {
if (row == -1 || row == grid.size()) return;
if (col == -1 || col == grid[row].size()) return;
if (visited[row][col]) return;
if (grid[row][col] != oc) return;
if (is_border(origin_grid, row, col)) {
grid[row][col] = color;
}
visited[row][col] = true;
helper(grid, origin_grid, visited, row+1, col, color);
helper(grid, origin_grid, visited, row-1, col, color);
helper(grid, origin_grid, visited, row, col+1, color);
helper(grid, origin_grid, visited, row, col-1, color);

}

bool is_border(vector<vector<int>> &grid, int row, int col) {
if (row == 0 || row == grid.size()-1) return true;
if (col == 0 || col == grid[row].size() - 1) return true;

if (grid[row][col] != grid[row+1][col] ||
grid[row][col] != grid[row-1][col] ||
grid[row][col] != grid[row][col+1] ||
grid[row][col] != grid[row][col-1]) {
return true;
}
return false;
}
private:
int oc = -1;
};