题目描述
红与黑(Flood Fill)
算法1
BFS宽搜 $O(n*m)$
- 找出矩阵中的起始点,即a[i][j]==’@’
- 对每个矩阵的起始点进行宽搜
(1)将起始点压入队列中,res=1;
(2)当队列不为空「
对队列的头部进行上下左右四个方向的搜索;
每搜到一个格子就压入队列中,res++;
」
注意点
- 注意题目中输入参数为:x轴方向的数目(列数),y轴方向的数目(行数;
- 注意题目输入....之间没有“ ”,所以将每个“.” or “@” or “#”输入进char矩阵a中时,都要先通过
String str = scanner.next();
获得每一行,再通过a[i][j] = str.charAt(j)
获得每个字符; - 一个.java文件中可以有多个类,但最多只能有一个被public修饰的class
- int res 不能设置为全局变量,要在BFS方法中设置,因为每个矩阵的输入都会求出一个res
JAVA 代码
import java.util.Scanner;
import java.util.*;
class Grid{
int x;
int y;
Grid(int x, int y){
this.x = x;
this.y = y;
}
}
public class Main{
static Scanner in = new Scanner(System.in);
static int N = 25;
static char[][] a = new char[N][N];
static int x=0,y=0,m=0,n=0,d=1;
static int[] dx={-1,0,1,0}, dy={0,1,0,-1};
public static int BFS(int sx,int sy){
Queue<Grid> q = new LinkedList<Grid>();
q.offer(new Grid(sx,sy));
a[sx][sy]='#';
int res=1;
while(!q.isEmpty()){
Grid t = q.poll();
for(int i=0;i<4;i++){
int c = t.x + dx[i];
int b = t.y + dy[i];
if(c<0||c>=n||b<0||b>=m||a[c][b]!='.') continue;
a[c][b] = '#';
q.offer(new Grid(c,b));
res++;
}
}
return res;
}
public static void main(String[] args){
while(true){
m = in.nextInt();//列数
n = in.nextInt();//行数
if(m==0&&n==0) break;
for(int i=0;i<n;i++){
String str = in.next();
for(int j=0;j<m;j++){
a[i][j] = str.charAt(j);
if(a[i][j] == '@'){
x=i;//这里的x,y与题目中的x轴,y轴不同,是指矩阵中的行数、列数
y=j;
}
}
}
System.out.println(BFS(x,y));
}
}
}
算法2
DFS深搜
- 找出矩阵的起始点
- 深搜,将遍历过的格子改为“#”,只要满足条件就res++
JAVA 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int x=0,y=0,m=0,n=0,N = 25;
static char[][] a = new char[N][N];
static int[] dx={-1,0,1,0},dy={0,1,0,-1};
public static int DFS(int x,int y){
a[x][y] = '#';
int res=1;
for(int i=0;i<4;i++){
int b = x+dx[i];
int c = y+dy[i];
if(b>=0&&b<n&&c>=0&&c<m&&a[b][c]=='.'){
res+=DFS(b,c);
}
}
return res;
}
public static void main(String[] args){
while(true){
m = in.nextInt();//列数
n = in.nextInt();//行数
if(m==0&&n==0) break;
for(int i=0;i<n;i++){
String str = in.next();
for(int j=0;j<m;j++){
a[i][j] = str.charAt(j);
if(a[i][j] == '@'){
x=i;
y=j;
}
}
}
System.out.println(DFS(x,y));
}
}
}