BFS
Java代码
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class Main {
//搜索到陆地,如果四个方向都有陆地,那么属于同一块岛屿
//因为子岛屿不计入岛屿总数,所以如果有子岛屿不用管,只需要保证搜索到的岛屿都不是子岛
//从边缘(也就是陆地外的海洋)搜索海洋,如果从八个方向搜索到岛屿,就一定不是子岛屿
//总结以上:就是从八个方向搜索边缘海洋,遇到陆地就从四个方向搜索完这座岛
static int n, m, num;
static int[][] ways = {{0, -1}, {-1, 0}, {0, 1}, {1, 0}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
static char[][] map = new char[52][52];
static boolean[][] flags = new boolean[52][52];
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int t = scanner.nextInt();
while(t > 0) {
for(int i = 0; i < map.length; i++) {
Arrays.fill(map[i], '0');
Arrays.fill(flags[i], false);
}
num = 0;
m = scanner.nextInt();
n = scanner.nextInt();
for(int i = 1; i <= m; i++) {
String tString = scanner.next();
for(int j = 1; j <= n; j++) {
map[i][j] = tString.charAt(j - 1);
}
}
bfs1(0, 0);
System.out.println(num);
t--;
}
}
//搜索海洋
public static void bfs1(int x, int y) {
Queue<Position> queue = new LinkedList<>();
queue.add(new Position(x, y));
flags[x][y] = true;
while(!queue.isEmpty()) {
Position tPosition = queue.poll();
for(int i = 0; i < 8; i++) {
int nx = tPosition.x + ways[i][0];
int ny = tPosition.y + ways[i][1];
if(nx >= 0 && ny >= 0 && nx <= m + 1 && ny <= n + 1 && !flags[nx][ny]) {
//遇到陆地就把与它相连的所有陆地块搜索完(也就是把整座岛搜索完)
if(map[nx][ny] == '1')
bfs2(nx, ny);
else {
flags[nx][ny] = true;
queue.add(new Position(nx, ny));
}
}
}
}
}
//搜索整座岛屿
public static void bfs2(int x, int y) {
num++;
flags[x][y] = true;
Queue<Position> queue = new LinkedList<>();
queue.add(new Position(x, y));
while(!queue.isEmpty()) {
Position tPosition = queue.poll();
for(int i = 0; i <4; i++) {
int nx = tPosition.x + ways[i][0];
int ny = tPosition.y + ways[i][1];
if(nx >= 0 && ny >= 0 && nx <= m + 1 && ny <= n + 1 && !flags[nx][ny] && map[nx][ny] == '1') {
queue.add(new Position(nx, ny));
flags[nx][ny] = true;
}
}
}
}
public static class Position{
int x;
int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
}
}