相聚 桂林电子科技大学第三届ACM程序设计竞赛

题目链接:https://ac.nowcoder.com/acm/contest/558/D

  就是求有多少块区域,用DFS就可以解决,一遇到一个1就从其开始深搜,将其所在的区域块覆灭(变为0),再遇到一个1,重复此操作。

Accept

import java.util.Scanner;

public class Main {

    static int old=0;
static int N;
static int M;
static char array[][];
static int x[]={-1,0,1,0}; //上左下右
static int y[]={0,1,0,-1}; static void solve(char array[][],int i,int j){
array[i][j]='0';
for(int d=0;d<4;d++){
int dx=i+x[d];
int dy=j+y[d];
if(dx<0 || dy<0 || dx>N-1 || dy>M-1){ //越界判断
continue;
}
if(array[dx][dy]=='1'){ //深搜覆盖这个岛屿
array[dx][dy]='0';
solve(array,dx,dy);
}
}
} public static void main(String[] args){
Scanner reader=new Scanner(System.in);
int T=reader.nextInt();
while(T>=1){
old=0;
N=reader.nextInt();
M=reader.nextInt();
array=new char[N][M];
for(int i=0;i<N;i++){
String s=reader.next();
array[i]=s.toCharArray();
}
// for(int i=0;i<N;i++){
// for(int j=0;j<M;j++){
// System.out.print(array[i][j]);
// }
// System.out.println();
// }
//第一次扫描
for(int i=0;i<N;i++){
for(int j=0;j<M;j++){
if(array[i][j]=='1'){
old++;
solve(array,i,j);
}
}
} System.out.println(old);
T--;
}
}
}
上一篇:springmvc乱码配置


下一篇:JAVA多线程下,获取递增的序列号