链接827. 最大人工岛 - 力扣LeetCode题解1、grid[i][j] 1 的节点visited里面存储的访问相同的岛屿标记为相同的tag2、counts记录的tag2count这个岛屿的数量是多大3、grid[i][j] 0的节点访问周围4个访问并且记录当前4周访问过的tags将当前岛屿的数量进行累加class Solution { public: int largestIsland(vectorvectorint grid) { int m grid.size(); if (m 0) { return 0; } int n grid[0].size(); if (n 0) { return 0; } vectorvectorint visited(m, vectorint(n, -1)); unordered_mapint, int counts; int result 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1 visited[i][j] -1) { int tag i * n j; counts[tag] bfs(i, j, m, n, grid, visited); result max(result, counts[tag]); } } } if (result 0) { return 1; } for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 0) { int tmp 1; unordered_setint tags; for (auto d : direc) { int next_x i d[0]; int next_y j d[1]; if (next_x 0 || next_y 0 || next_x m || next_y n || grid[next_x][next_y] ! 1 || tags.find(visited[next_x][next_y]) ! tags.end()) { continue; } tmp counts[visited[next_x][next_y]]; tags.insert(visited[next_x][next_y]); } result max(result, tmp); } } } return result; } vectorvectorint direc{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; int bfs(int x, int y, int m, int n, const vectorvectorint grid, vectorvectorint visited) { queueint que; que.push(x * n y); int tag x * n y; visited[x][y] tag; int result 1; while (!que.empty()) { auto f que.front(); que.pop(); for (auto d : direc) { int next_x f / n d[0]; int next_y f % n d[1]; if (next_x 0 || next_y 0 || next_x m || next_y n || visited[next_x][next_y] ! -1 || grid[next_x][next_y] ! 1) { continue; } visited[next_x][next_y] tag; que.push(next_x * n next_y); result; } } return result; } };
