Coloring A Border LeetCode solution in C++

1
// marking element -ve and then fix it while backtracking worked as visited
2
// matrix marking element 1e9 and not fixing it while backtracking works for
3
// coloring element
4
class Solution {
5
 private:
6
  int m, n;
7

8
 public:
9
  bool is_valid(int i, int j, vector<vector<int>> &grid, int org_color) {
10
    return i >= 0 and j >= 0 and i < m and j < n and grid[i][j] == org_color and grid[i][j] > 0;
11
  }
12

13
  bool is_colorable(int i, int j, vector<vector<int>> &grid, int org_color) {
14
    if (i == 0 or j == 0 or i == m - 1 or j == n - 1) return true; // boundary condn
15

16
    // checking any of the neighbour is of opposite color or not
17
    if (i - 1 >= 0 and abs(grid[i - 1][j]) != org_color and grid[i - 1][j] != 1e9) return true;
18

19
    if (i + 1 < m and abs(grid[i + 1][j]) != org_color and grid[i + 1][j] != 1e9) return true;
20

21
    if (j - 1 >= 0 and abs(grid[i][j - 1]) != org_color and grid[i][j - 1] != 1e9) return true;
22

23
    if (j + 1 < n and abs(grid[i][j + 1]) != org_color and grid[i][j + 1] != 1e9) return true;
24

25
    return false;
26
  }
27

28
  void dfs(int i, int j, vector<vector<int>> &grid, int org_color) {
29
    if (!is_valid(i, j, grid, org_color)) return;
30

31
    if (is_colorable(i, j, grid, org_color))
32
      grid[i][j] = 1e9;
33
    else
34
      grid[i][j] = -grid[i][j];
35

36
    dfs(i - 1, j, grid, org_color);
37
    dfs(i + 1, j, grid, org_color); // up and down
38
    dfs(i, j - 1, grid, org_color);
39
    dfs(i, j + 1, grid, org_color); // left and right
40

41
    if (grid[i][j] < 0) grid[i][j] = -grid[i][j];
42
  }
43
  vector<vector<int>> colorBorder(vector<vector<int>> &grid, int row, int col, int color) {
44
    m = grid.size(), n = grid[0].size();
45
    dfs(row, col, grid, grid[row][col]);
46
    for (auto &it : grid) {
47
      for (auto &i : it) {
48
        if (i == 1e9) i = color;
49
      }
50
    }
51
    return grid;
52
  }
53
};