岛屿问题和昆虫越障问题以及岛屿最大面积
程序员文章站
2022-06-27 16:11:58
岛屿问题题目地址: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