Flood Fill 洪水灌溉算法
BFS
模板:
while 队列非空{
取出队头;
枚举队头的四个邻格{
if 各格子是陆地且为被开发过
标记为开发过
插入队列
}
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time:2021年1月14日 下午10:01:17
*
*/
class Node{
int x, y;
public Node(int x, int y) {//注意赋值是最好用this.
this.x = x;
this.y = y;
}
}
public class Main {
//顺时针方向
static int dir[][] = {{-1,0},{0,1},{1,0},{0,-1}};
static int N = 25;
static int m;
static int n;
static char[][] map = new char[N][N];
public static int bfs(int sx,int sy) {
int cnt = 1;
Queue<Node> q = new LinkedList<Node>();
//标记为已经访问过
q.add(new Node(sx, sy));
//标记为红砖
map[sx][sy] = '#';
while(! q.isEmpty()) {
//取出队头
Node node = q.peek();
q.poll();
//枚举队头的四个邻格
for(int i = 0; i < 4; i++) {
int nx = node.x + dir[i][0];
int ny = node.y + dir[i][1];
//越界或者访问过或者不为黑砖
if(nx < 0 || nx >= m || ny < 0 || ny >=n || map[nx][ny]!='.')
continue;
//应该在此处标记访问过
map[nx][ny] = '#';
q.offer(new Node(nx,ny));
cnt ++;
}
}
return cnt;
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
while(true) {
n = reader.nextInt(); //列
m = reader.nextInt(); //行
if( m ==0|| n == 0)
break;
int sx = 0, sy = 0;
for(int i = 0; i < m; i++) {
String s = reader.next();
for(int j = 0; j < n; j++) {
map [i][j] = s.charAt(j);
if(map [i][j] == '@') {
sx = i;
sy = j;
}
}
}
System.out.println(bfs(sx, sy) );
}
}
}
DFS
模板
dfs(x,y){
将(x,y)标记为开发;
枚举(x,y)的4个邻格;
if 邻格可走
dfs(邻格);
}
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
/**
* @author JohnnyLin
* @version Creation Time:2021年1月14日 下午10:01:17
*
*/
public class Main {
//顺时针方向
static int dir[][] = {{-1,0},{0,1},{1,0},{0,-1}};
static int N = 25;
static int m;
static int n;
static char[][] map = new char[N][N];
static boolean[][] vis = new boolean[N][N];//记录该点是否遍历过
public static int dfs(int sx,int sy) {
int res = 1;
map[sx][sy] = '#';
//枚举(sx,sy)的四个邻格
for(int i = 0; i < 4; i++) {
//如果邻格可走
int nx = sx + dir[i][0], ny = sy +dir[i][1];
if(nx >= 0 && nx < m && ny >= 0 && ny < n && map[nx][ny] =='.') {
res += dfs(nx, ny);
}
}
return res;
}
public static void main(String[] args) {
Scanner reader = new Scanner(System.in);
while(true) {
n = reader.nextInt(); //列
m = reader.nextInt(); //行
if( m ==0|| n == 0)
break;
int sx = 0, sy = 0;
for(int i = 0; i < m; i++) {
String s = reader.next();
for(int j = 0; j < n; j++) {
map [i][j] = s.charAt(j);
if(map [i][j] == '@') {
sx = i;
sy = j;
}
}
}
System.out.println(dfs(sx, sy) );
}
}
}