The problem

Making A Large Island Hard

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.
Copy the code

Example 2:

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.
Copy the code

Example 3:

Input: grid = [[1,1],[1,1]]
Output: 4
Explanation: Can't change any 0 to 1, only one island with area = 4.
Copy the code

 

Constraints:

  • n == grid.length
  • n == grid[i].length
  • 1 <= n <= 500
  • grid[i][j] is either 0 or 1.

Their thinking

The question can be broken down into two sub-questions:

  1. Identify and mark each island and calculate its size
  2. Try to reclaim land from the sea, connect adjacent islands, and get the largest artificial island possible (use sub-problems whenever possible1The area of the island)

For subproblem 1, we note that the definition of an island is that all land bordering in four directions represents an island, and 1 in the grid represents land. We can do this:

  1. traversegridUntil it hits land, i.egrid[row][col] == 1
  2. Start by looking for all the land that borders it, and add up the number of landmasses that you have traveled to calculate the size of the island until you have covered every inch of land that borders it
  3. Repeat the steps until you have traversedgrid, need to pay attention to the steps1You need to skip steps already in progress2Land marked with demerits

In order to use the calculation results in subquestion 1 in subquestion 2, we need to distinguish different islands, so we need to number the islands and save the area corresponding to the island number, for example, List

islandAreaList to save the island area. At the same time, you need to record which land in the grid belongs to which island. We noticed that the “1” in the grid for land was no longer needed to calculate the size of the island. We could reuse the island number and save it in the island grid. Since 0 and 1 are already used, the island number should start with 2.

In addition, in order to find all of the land adjacent to one land, you need to use depth-first search (DFS), which is an algorithm for traversing or searching trees or graphs. The algorithm searches branches of the tree as deep as possible until all nodes reachable from the source node have been found. Grid [row][col] can be set to an island number. If the island number is >=2, grid[row][col] == 1 cannot be accessed. At this point we are almost done with subproblem 1.

For subproblem 2, we can do this:

  1. traversegridUntil it hits the ocean, i.egrid[row][col] == 0
  2. fromgridFind the numbers of all the islands next to it,Note that island numbers cannot be repeated
  3. Use island numbering fromislandAreaListTo get the corresponding island area
  4. The artificial island area was accumulated and the maximum artificial island area was recorded

Refer to the answer

public class Solution {

    // 4 directions connected to one cell
    final int[] rowBoundary = {-1.1.0.0};
    final int[] colBoundary = { 0.0, -1.1};

    public int largestIsland(int[][] grid) {
        int n = grid.length;

        List<Integer> islandAreaList = new ArrayList<>();
        // make initial list size to 2
        islandAreaList.add(-1);
        islandAreaList.add(-1);

        int maxArea = 0;

        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 1) {
                    intarea = DFS(row, col, grid, islandAreaList.size()); islandAreaList.add(area); maxArea = area; }}}// a set to save island No. during connecting islands, to avoid duplicate sum
        HashSet<Integer> islandSet = new HashSet<>();
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (grid[row][col] == 0) {

                    int sum = 0;
                    islandSet.clear();

                    // move to connected cells
                    for (int i = 0; i < rowBoundary.length; i++) {
                        int r = row + rowBoundary[i];
                        int c = col + colBoundary[i];
                        // island area can be only summed by once
                        if (isValid(r, c, grid) && grid[r][c] > 0&&! islandSet.contains(grid[r][c])) { sum += islandAreaList.get(grid[r][c]); islandSet.add(grid[r][c]); }}// the final area should +1 since we change current 0 to 1
                    if (sum + 1 > maxArea) {
                        maxArea = sum + 1; }}}}return maxArea == 0 ? 1 : maxArea;
    }

    private int DFS(int row, int col, int[][] grid, int islandNo) {

        // set the islandNo to grid
        grid[row][col] = islandNo;
        // the area of the island
        int area = 1;

        // move to connected cells
        for (int i = 0; i < rowBoundary.length; i++) {
            int r = row + rowBoundary[i];
            int c = col + colBoundary[i];
            if (isValid(r, c, grid) && grid[r][c] == 1) { area += DFS(r, c, grid, islandNo); }}return area;
    }

    private boolean isValid(int row, int col, int[][] grid) {
        return row >= 0 && row < grid.length && col >=0 && col < grid[0].length; }}Copy the code

Expand training

Try the same DFS problem!

[Leetcode] [Medium] Count Good Nodes in Binary Tree Good statistics in the Binary Tree node, the number of | Java

Or check out the author’s LeetCode column for additional questions of interest!

Juejin. Cn/column / 6997…

The data link

  • The original problem

Leetcode.com/problems/ma…

  • Depth-first search

Zh.wikipedia.org/wiki/%E6%B7…