岛屿问题和昆虫越障问题以及岛屿最大面积

岛屿问题

题目地址：https://leetcode-cn.com/problems/number-of-islands/submissions/

package A.giao;

public class demo200 {
    public static void main(String[] args) {
        String str0="11110";
        String str1="11110";
        String str2="11110";
        String str3="11110";

        char[][] grid=new char[4][];//定义二维字符数组

        grid[0]=str0.toCharArray();
        grid[1]=str1.toCharArray();
        grid[2]=str2.toCharArray();
        grid[3]=str3.toCharArray();

        System.out.println(numIslands(grid));


    }
    public static int numIslands(char[][] grid){
        int a=grid.length;
        int b=grid[0].length;

        int count=0;

        for(int i=0;i<a;i++){
            for(int j=0;j<b;j++){
                if(grid[i][j]=='1'){
                    ++count;
                    dfs(grid,i,j);
                }
            }
        }
        return count;
    }

    public static void dfs(char[][] array,int i,int j){
        int a=array.length;
        int b=array[0].length;

        if(i<0||j<0||i>=a||j>=b||array[i][j]=='0'){
            return;
        }

        array[i][j]='0';

        dfs(array,i-1,j);
        dfs(array,i+1,j);
        dfs(array,i,j-1);
        dfs(array,i,j+1);
    }
}

岛屿最大面积

题目链接：https://leetcode-cn.com/problems/max-area-of-island/

    public int maxAreaOfIsland(int[][] grid) {
        int max = 0;
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(grid[i][j] == 1){
                    max = Math.max (dfs(grid, i, j), max);
                }
            }
        }
        return max;
    }
    int dfs(int[][] grid, int i, int j){
        if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0){
            return 0;
        }
        grid[i][j] = 0;
        int count = 1;
        count += dfs(grid, i+1, j);
        count += dfs(grid, i-1, j);
        count += dfs(grid, i, j+1);
        count += dfs(grid, i, j-1);
        return count;
    }

跟岛屿问题一样，由于判断最大的岛屿块，所以不用回溯到原状态，状态转移时候，如果条件符合，结果数递增

昆虫越障问题

题目链接：https://shimo.im/docs/R13j8bP2LjIX5Ek5/read
昆虫越障问题就是岛屿问题的变形，修改几个出口信息就行

package A.giao;

import java.util.Scanner;

public class demo01 {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int T=sc.nextInt();
        for(int i=0;i<T;i++){
            int N=sc.nextInt();
            int M=sc.nextInt();

            char[][] array=new char[N][M];//定义二维字符数组
            boolean[][] used = new boolean[N][M];
            for(int j=0;j<N;j++){
                //每一行有一个长度为M的字符串
                    array[j]=sc.next().toCharArray();
            }
            result = Integer.MAX_VALUE;
            //定位位置
            for(int q=0;q<N;q++){
                for(int p=0;p<M;p++){
                    if(array[q][p]=='@'){
                       toResult(array, q, p,0,used);
                    }
                }
            }
            if(result == Integer.MAX_VALUE) {
                System.out.println(-1);
            }else{
                System.out.println(result);
            }
        }
    }

    static int result;
    public static void toResult(char[][] array, int i, int j,int res,boolean[][] used){

        if(i<0||i>=array.length||j<0||j>=array[0].length){
            result=Math.min(res,result);
            return;
        }

        //无法通过
        if(array[i][j]=='#'||used[i][j]==true){
            return;
        }

        //拆除障碍物
        if(array[i][j]=='*')
            res++;

        used[i][j]=true;
        toResult(array,i+1,j,res,used);
        toResult(array,i-1,j,res,used);
        toResult(array,i,j+1,res,used);
        toResult(array,i,j-1,res,used);
        used[i][j]=false;
    }
}

本文地址：https://blog.csdn.net/Zhangjiangyuan/article/details/109893598