第一题:岛屿数量
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) 回帖