制作一个大岛 leetcode - 发现错误 Java

Question

我正在研究 LeetCode 问题 827. Making A Large Island:

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.

Example 1:

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.

对于以下测试用例，我的解决方案失败了：

[[1,1,0],[0,0,0], [1,1,0]]

我的代码的输出是 3，但预期是 5。

这是我的代码：

class Solution {
    public int largestIsland(int[][] grid) {
        int n=grid.length;
        int max=0;
        boolean hasZero=false;
        boolean[][] visited = new boolean[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(grid[i][j]==0){
                    grid[i][j]=1;
                    max=Math.max(max,area(grid,n,i,j,visited));  
                    grid[i][j]=0;
                   // visited[i][j]=false;
                    hasZero=true;
                }
            }
        }
        
        return hasZero?max:n*n;
    }
    
    private int area(int[][] grid, int n, int i, int j, boolean[][] visited){
        if(i<0 || i>n-1 || j>n-1 || j<0 || grid[i][j]==0 || visited[i][j])
            return 0;
        
        visited[i][j]=true;
        int a1 =  area(grid,n,i+1,j,visited);
        int a2 =  area(grid,n,i,j+1,visited);
        int a3 = area(grid,n,i-1,j,visited);
        int a4 =  area(grid,n,i,j-1,visited);
            
        return 1+a1+a2+a3+a4;
    }
}

这个解决方案是 O(N^4)，我知道其他更有效的工作解决方案，但我无法发现我的尝试有什么问题。

有人能找出问题所在吗？

Answer 1

问题是当你将一个岛标记为已访问后，它就不能再发挥更好的连接作用了。

例如，您失败的测试用例：

[[1, 1, ],[0, 0, 0],[1, 1, 0]]

...可以描述为：

 1 1 0
 0 0 0
 1 1 0

您的代码将首先尝试这个（更改括号中的值）：

 1 1(1)
 0 0 0
 1 1 0

...并将那些标记为已访问（我将标记为“v”）：

 v v v
 0 0 0
 1 1 0

...所以它为 max.

找到 3

然后它将继续查找以下内容：

 v v v
(1)0 0
 1 1 0

这将导致值为 3，这不会提高 max 的先前值。但这是错误的，因为它确实与您标记为访问过的另一个岛屿相连。它应该找到这个：

 1 1 0
(1)0 0
 1 1 0

... 即 5.

由于您已经找到了可行的算法，我想这可以回答您的问题。

制作一个大岛 leetcode - 发现错误 Java

Making a island large leetcode - spotting mistake Java

java

algorithm

graph

data-structures

Example 1: