欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2022-03-16 14:52:14
岛屿问题题目地址: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"; St...

岛屿问题

题目地址: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