Problem: 827. Making A Large Island 最大人工岛
解题过程
首先统计了所有的1区块，并将坐标放入列表中，对每个区块，拿到距离最近的两个点坐标，若是abs(x-xx) + abs(y-yy)==2，则表示可以connected，将可能的grid[i][j]==0点放入哈希表并累加计数，这种方式比较慢，超时了
最后用了标记的方式，对每个区块标记一个记号，并用哈希表记录这个记号对应的区块大小，对每个grid[i][j]==0，上下左右累加哈希表中记号对应的大小即可，不能重复累加同一个标记区块，拿到最大值即可，计算量大大减小了
Code
class Solution { public: vector<vector<bool>> status; int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}, n; int cnt = 0, cntcnt = 100; unordered_map<int, int> umpump; void dfs(vector<vector<int>>& grid, int x, int y) { status[x][y] = true; int xx, yy; cnt++; for(int i = 0; i < 4; i++) { xx = x + dir[i][0]; yy = y + dir[i][1]; if(xx>=0 && yy>=0 && xx < n && yy < n && grid[xx][yy]==1 && status[xx][yy]==false) { dfs(grid, xx, yy); } } grid[x][y] = cntcnt; } int largestIsland(vector<vector<int>>& grid) { n = grid.size(); status.assign(n, vector<bool>(n, false)); bool zero = false; int mx = INT_MIN; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(grid[i][j] == 1 && status[i][j] == false) { cnt = 0; cntcnt++; dfs(grid, i, j); umpump[cntcnt] = cnt; mx = max(mx, cnt); } if(grid[i][j]==zero) zero = true; } } if(umpump.size()==1) { return mx + (int)zero; } if(umpump.size()==0) { return (int)zero; } int x, y; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { if(grid[i][j] == 0) { int sum = 1; unordered_set<int> te; for(int k = 0; k < 4; k++) { x = i + dir[k][0]; y = j + dir[k][1]; if(x >= 0 && y >= 0 && x < n && y < n && grid[x][y]!=0) { if(te.find(grid[x][y]) == te.end()) { sum += umpump[grid[x][y]]; } te.insert(grid[x][y]); } } mx = max(mx, sum); } } } return mx; // for(int i = 0; i < tr.size(); i++) { // mx = max(mx, (int)tr[i].size()); // } // unordered_map<int, unordered_set<int>> ump; // int x, y, tx, ty, px, py; // vector<pair<int, int>> p1, p2; // float d1, d2, dis; // for(int i = 0; i < tr.size(); i++) { // p1 = tr[i]; // for(int j = i + 1; j < tr.size(); j++) { // p2 = tr[j]; // for(int k = 0; k < tr[i].size(); k++) { // tx = p1[k].first; // ty = p1[k].second; // for(int w = 0; w < tr[j].size(); w++) { // px = p2[w].first; // py = p2[w].second; // d1 = tx - px; // d2 = ty - py; // dis = abs(d1) + abs(d2); // if(dis == 2.0) { // x = (tx + px) / 2; // y = (ty + py) / 2; // if(tx == px || ty == py) { // ump[(x<<10) + y].insert(i); // ump[(x<<10) + y].insert(j); // } else { // ump[(tx<<10) + py].insert(i); // ump[(tx<<10) + py].insert(j); // ump[(px<<10) + ty].insert(i); // ump[(px<<10) + ty].insert(j); // } // } // } // } // } // } // for(auto [k, l] : ump) { // int sum = 1; // for(auto in : l) { // sum += (int)tr[in].size(); // } // mx = max(sum, mx); // } // return mx; } };
