Nuggets team number online, help you Offer impromptu! Click for details

I. Title Description:

Given an m x n 2d grid map of '1's (land) and '0's (water), return the number of islands which the sum of 1's on the island equal S (S>0). An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume  all four edges of the grid are all surrounded by water. Example 1: Input: grid= [["1"."1"."1"."1"."0"],
  ["1"."1"."0"."1"."0"],
  ["1"."1"."0"."0"."0"],
  ["0"."0"."0"."0"."0"]
], S = 9
Output: 1
public int sumIslands(char[][] grid, int S){
    // implementation
}
//----------
// unit test
//----------
Tip: using Junit4.
public void sumIslandsTest(a){
    char[][] grid = [
    ["1"."1"."1"."1"."0"],
    ["1"."1"."0"."1"."0"],
    ["1"."1"."0"."0"."0"],
    ["0"."0"."0"."0"."0"]].int S = 8;
    // test implementation
}
Copy the code

Ii. Analysis of Ideas:

A minor variation on the island problem, from counting how many islands there are to counting how big the islands are.

A complete DFS

  1. Determine exit conditions (illegal or legal)
  2. Record accessed
  3. Return recurses to other points

Here illegal means out of bounds, legal means the point has been traversed

Iii. AC Code:

package com.company;

public class * {
    public int sizer;
    public int sizel;
    public int sumIslands(char[][] grid, int S){
        // implementation
        this.sizer = grid.length;
        this.sizel = grid[0].length;
        int ret = 0;
        for (int i = 0; i < grid.length; i++){
            for (int j = 0; j < grid[0].length; j++){
                int tmp = dfs(grid, i, j);
                if(tmp == S)ret++; }}return ret;
    }
    public int dfs(char[][] grid, int r, int l){
        / / illegal
        if(r >= sizer || r < 0 || l < 0 || l >= sizel){
            return 0;
        }
        // Not an island or already traversed
        if(grid[r][l] ! =1) {return 0;
        }
        grid[r][l] = 2;
        return 1 + dfs(grid,r + 1, l)+ dfs(grid,r , l + 1)+ dfs(grid,r - 1, l)+ dfs(grid,r, l - 1);
    }
//----------
// unit test
//----------
// Tip: using Junit4.
    public void sumIslandsTest(a){
        char[][] grid = {
                {'1'.'1'.'1'.'1'.'0'},
                {'1'.'1'.'0'.'1'.'0'},
                {'1'.'1'.'0'.'0'.'0'},
                {'0'.'0'.'0'.'0'.'0'}};int S = 8;
        // test implementation
        Return 0 since S = 8 and island = 9
        System.out.println(sumIslands(grid,S));
    }

    public static void main(String[] args) {
        * v = new *();
        v.sumIslandsTest();
    }
}

Copy the code

Iv. Summary:

Because of the resistance to backtracking and recursion, EVERY time I encounter this kind of problem, I think about bit operation, and check the set of SAO routines, so eat a lot of losses, I hope you do not take my old road.