题目

104. 建造最大岛屿 (kamacoder.com)

代码（ACM 首刷看解析）：

#include<iostream>
#include<vector>
#include<unordered_map>
#include<unordered_set>
using namespace std;int dir[4][2] = {1,0,-1,0,0,1,0,-1};
int count;
int n, m;
void dfs(vector<vector<int>>&grid, int mark, int row, int col) {grid[row][col] = mark;count++;for (int i = 0; i < 4; i++) {int newRow = row + dir[i][0];int newCol = col + dir[i][1];if (newRow < 0 || newRow >= n || newCol < 0 || newCol >= m) continue;if (grid[newRow][newCol] != 1) continue;dfs(grid, mark, newRow, newCol);}
}void print(vector<vector<int>>& arr, int n, int m) {for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cout << arr[i][j] <<" ";}cout << endl;}
}int main() {cin >> n >> m;vector<vector<int>> grid(n, vector<int>(m));for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {cin >> grid[i][j];}}// print(grid, n, m);// cout<<endl;// 先遍历一遍，获得所有岛屿的最大值int mark = 2;count = 0;unordered_map<int,int> myMap;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 1) {dfs(grid, mark, i, j);myMap[mark] = count;mark++;count = 0;}}}//print(grid, n, m);int maxResult = 0;unordered_set<int> us;bool AllisGrid = true;for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 0) {AllisGrid = false;int tmp = 0;for (int k = 0; k < 4; k++) {int newI = i + dir[k][0];int newJ = j + dir[k][1];if (newI < 0 || newI >= n || newJ < 0 || newJ >= m) continue;if (us.find(grid[newI][newJ]) == us.end()) {tmp += myMap[grid[newI][newJ]];us.insert(grid[newI][newJ]);}}maxResult = max(tmp + 1, maxResult);us.clear();// cout << endl;// cout << "grid[" << i << "][" << j << "]:" << tmp << endl;} }}if (AllisGrid) cout << n * m << endl;else cout << maxResult << endl;return 0;
}