Making A Large Island LeetCode solution in C++

1
class Solution {
2
  int dir[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
3

4
  bool isValid(vector<vector<int>> const &grid, vector<vector<int>> &visited, int row, int col) {
5
    int n = grid.size();
6

7
    if (row < 0 || row >= n || col < 0 || col >= n || grid[row][col] != 1 ||
8
        visited[row][col] != 0) {
9
      return false;
10
    }
11
    return true;
12
  }
13

14
  int helper(vector<vector<int>> const &grid, vector<vector<int>> &visited, int row, int col) {
15
    if (!isValid(grid, visited, row, col)) return 0;
16

17
    visited[row][col] = 1;
18

19
    return 1 + helper(grid, visited, row + dir[0][0], col + dir[0][1]) +
20
           helper(grid, visited, row + dir[1][0], col + dir[1][1]) +
21
           helper(grid, visited, row + dir[2][0], col + dir[2][1]) +
22
           helper(grid, visited, row + dir[3][0], col + dir[3][1]);
23

24
    return 0;
25
  }
26

27
 public:
28
  int largestIsland(vector<vector<int>> &grid) {
29
    int ans = 0;
30
    int n = grid.size();
31
    for (int i = 0; i < n; i++) {
32
      for (int j = 0; j < grid.size(); j++) {
33
        if (grid[i][j] == 0) {
34
          grid[i][j] = 1;
35
          vector<vector<int>> visited(n, vector<int>(n, 0));
36
          ans = max(ans, helper(grid, visited, i, j));
37
          grid[i][j] = 0;
38
        }
39
      }
40
    }
41
    return ans == 0 ? n * n : ans;
42
  }
43
};