题目描述
You are given an n x n binary matrix grid. You are allowed to change at most one 0 to be 1.
Return the size of the largest island in grid after applying this operation.
An island is a 4-directionally connected group of 1s.
Example1:
Input: grid = [[1,1],[1,0]] Output: 4 Explanation: Change the 0 to 1 and make the island bigger, only one island with area = 4.
Example2:
Input: grid = [[1,0],[0,1]] Output: 3 Explanation: Change one 0 to 1 and connect two 1s, then we get an island with area = 3.
Example3:
Input: grid = [[1,1],[1,1]] Output: 4 Explanation: Can’t change any 0 to 1, only one island with area = 4.
NOTE
- n == grid.length
- n == grid[i].length
- 1 <= n <= 500
- grid[i][j] is either 0 or 1.
解题思路
- 简单DFS遍历
常规DFS 会报超时 共过69/75个测试用例
class Solution {
public:
int largestIsland(vector<vector<int>>& grid) {
if(grid.size() == 0){
return 0;
}
int row = grid.size();
int col = grid[0].size();
if(col == 0){
return 0;
}
int res = 0;
int flag = 0;
bool isVisit[row * col];
for(int i = 0; i < row * col; i++){
isVisit[i] = false;
}
for(int i = 0; i < row; i++){
for(int j = 0; j < col; j++){
int temp = 0;
if(grid[i][j] == 0){
grid[i][j] = 1;
flag = 1;
}
dfs(i, j, row, col, isVisit, temp, grid);
if(flag == 1){
grid[i][j] = 0;
flag = 0;
}
if(temp > res){
res = temp;
}
}
}
return res;
}
void dfs(int r, int c, int row, int col, bool* isVisit, int& res, vector<vector<int>>& grid){
if(r < 0 || r >= row || c < 0 || c >= col || isVisit[r * col + c] == true || grid[r][c] == 0){
return;
}
res++;
isVisit[r * col + c] = true;
dfs(r - 1, c, row, col, isVisit, res, grid);
dfs(r + 1, c, row, col, isVisit, res, grid);
dfs(r, c + 1, row, col, isVisit, res, grid);
dfs(r, c - 1, row, col, isVisit, res, grid);
isVisit[r * col + c] = false;
}
};
改进版本
