leetcode-cpp/0827.cpp at main · s4nj1th/leetcode-cpp · GitHub

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
class Solution {
private:
  int exploreIsland(vector<vector<int>> &grid, int islandId, int currentRow,
                    int currentColumn) {
    if (currentRow < 0 || currentRow >= grid.size() || currentColumn < 0 ||
        currentColumn >= grid[0].size() || grid[currentRow][currentColumn] != 1)
      return 0;

    grid[currentRow][currentColumn] = islandId;
    return 1 + exploreIsland(grid, islandId, currentRow + 1, currentColumn) +
           exploreIsland(grid, islandId, currentRow - 1, currentColumn) +
           exploreIsland(grid, islandId, currentRow, currentColumn + 1) +
           exploreIsland(grid, islandId, currentRow, currentColumn - 1);
  }

public:
  int largestIsland(vector<vector<int>> &grid) {
    unordered_map<int, int> islandSizes;
    int islandId = 2;

    for (int currentRow = 0; currentRow < grid.size(); ++currentRow) {
      for (int currentColumn = 0; currentColumn < grid[0].size();
           ++currentColumn) {
        if (grid[currentRow][currentColumn] == 1) {
          islandSizes[islandId] =
              exploreIsland(grid, islandId, currentRow, currentColumn);
          ++islandId;
        }
      }
    }

    if (islandSizes.empty()) {
      return 1;
    }

    if (islandSizes.size() == 1) {
      --islandId;
      return (islandSizes[islandId] == grid.size() * grid[0].size())
                 ? islandSizes[islandId]
                 : islandSizes[islandId] + 1;
    }

    int maxIslandSize = 1;

    for (int currentRow = 0; currentRow < grid.size(); ++currentRow) {
      for (int currentColumn = 0; currentColumn < grid[0].size();
           ++currentColumn) {
        if (grid[currentRow][currentColumn] == 0) {
          int currentIslandSize = 1;
          unordered_set<int> neighboringIslands;

          if (currentRow + 1 < grid.size() &&
              grid[currentRow + 1][currentColumn] > 1) {
            neighboringIslands.insert(grid[currentRow + 1][currentColumn]);
          }

          if (currentRow - 1 >= 0 && grid[currentRow - 1][currentColumn] > 1) {
            neighboringIslands.insert(grid[currentRow - 1][currentColumn]);
          }

          if (currentColumn + 1 < grid[0].size() &&
              grid[currentRow][currentColumn + 1] > 1) {
            neighboringIslands.insert(grid[currentRow][currentColumn + 1]);
          }

          if (currentColumn - 1 >= 0 &&
              grid[currentRow][currentColumn - 1] > 1) {
            neighboringIslands.insert(grid[currentRow][currentColumn - 1]);
          }

          for (int id : neighboringIslands) {
            currentIslandSize += islandSizes[id];
          }

          maxIslandSize = max(maxIslandSize, currentIslandSize);
        }
      }
    }

    return maxIslandSize;
  }
};