题目描述
blablabla
算法1
dfs
时间复杂度
$O(n^2)$
参考文献
Java代码
import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
static int[] dx={1,-1,0,0};
static int[] dy={0,0,1,-1};
static boolean[][] visit;
static int ans=0;
static boolean flag=false;
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
//在此输入您的代码...
int n=scan.nextInt();
char[][] arr=new char[n][n];
for(int i=0;i<n;i++){
arr[i]=scan.next().toCharArray();
}
visit=new boolean[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(arr[i][j]=='#'&&!visit[i][j]){
dfs(arr,i,j);
if(!flag)ans++;
flag=false;
}
}
}
System.out.print(ans);
scan.close();
}
static void dfs(char[][] arr,int a,int b){
if(check(arr,a+dx[0],b+dy[0])&&check(arr,a+dx[1],b+dy[1])&&check(arr,a+dx[2],b+dy[2])&&check(arr,a+dx[3],b+dy[3])){
flag=true;//上下左右都是大陆,没有被淹没
}
visit[a][b]=true;
for(int i=0;i<4;i++){
int newX=a+dx[i];
int newY=b+dy[i];
if(arr[newX][newY]=='#'&&!visit[newX][newY])dfs(arr,newX,newY);//把该片岛屿访问完
}
}
static boolean check(char[][] arr,int i,int j){
return arr[i][j]=='#';
}
}
```