第一题:岛屿数量
package Test; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.LinkedList; class node{ int x; int y; public node(int x,int y){ this.x=x; this.y=y; } } public class 岛屿数量 { public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String[] str=br.readLine().split(","); int[][] map=new int[str.length][str[0].length()]; for(int i=0;i<str.length;i++){ for(int j=0;j<str[i].length();j++){ map[i][j]=str[i].charAt(j)-'0'; } } int[][] vis=new int[str.length][str[0].length()]; int m=vis.length,n=vis[0].length,flag=0; for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(map[i][j]==1&&vis[i][j]==0){ bfs(map,vis,m,n,i,j); flag++; } } } System.out.println(flag); } public static void bfs(int[][] map,int[][] vis,int m,int n,int x,int y){ LinkedList<node>q=new LinkedList<>(); q.offer(new node(x,y)); while(!q.isEmpty()){ node temp=q.pop(); if(temp.x+1<m&&map[temp.x+1][temp.y]==1&&vis[temp.x+1][temp.y]==0){ vis[temp.x+1][temp.y]=1; q.offer(new node(temp.x+1,temp.y)); } if(temp.y+1<n&&map[temp.x][temp.y+1]==1&&vis[temp.x][temp.y+1]==0){ vis[temp.x][temp.y+1]=1; q.offer(new node(temp.x,temp.y+1)); } } } }第二题:戳气球
package Test; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List; public class 戳气球 { private static int maxn=0; public static void main(String[] args) throws IOException { BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); String[] str=br.readLine().split(","); List<Integer>list=new ArrayList<>(); for(int i=0;i<str.length;i++){ list.add(Integer.parseInt(str[i])); } dfs(list,0); System.out.println(maxn); } public static void dfs(List<Integer>list,int flag){ if(list.size()==0){ maxn=Math.max(maxn,flag); return; } if(list.size()==1){ List<Integer>temp=new ArrayList<>(list); temp.remove(0); dfs(temp,flag+list.get(0)); } else if(list.size()==2){ List<Integer>temp=new ArrayList<>(list); if(list.get(0)<list.get(1)){ temp.remove(0); dfs(temp,flag+list.get(0)*list.get(1)); } else{ temp.remove(1); dfs(temp,flag+list.get(0)*list.get(1)); } } else{ for(int i=1;i<list.size()-1;i++){ List<Integer>temp=new ArrayList<>(list); temp.remove(i); dfs(temp,flag+list.get(i)*list.get(i-1)*list.get(i+1)); } } } }
全部评论
(5) 回帖