BFS 宽度优先遍历
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Main {
//BFS 宽度优先遍历
static int row,col,res;
static char[][] array=new char[25][25];
//上 右 下 左
static int[] dx= {-1,0,1,0};
static int[] dy= {0,1,0,-1};
//队列储存的是当前的坐标
static Queue<int[]> queue=new LinkedList<>();
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
// 输入列行 空格隔开
String[] str1 = br.readLine().split(" ");
col=Integer.parseInt(str1[0]);
row=Integer.parseInt(str1[1]);
//最后输入0 0 结束输出
if(col==0&&row==0) break;
//初始化数组array,并找到当前坐标@
int x=0,y=0;
for(int i=0;i<row;i++) {
//输入一行 没有空格
String str2 = br.readLine();
for(int j=0;j<col;j++) {
array[i][j]=str2.charAt(j);
if(array[i][j]=='@') {
x=i;y=j;
}
}
}
System.out.println(bfs(x,y));
}
}
public static int bfs(int x,int y) {
queue.offer(new int[] {x,y});
res=0;
//标记当前坐标已经走过
array[x][y]='#';
while(!queue.isEmpty()) {
int[] poll=queue.poll();
res++;
for(int i=0;i<4;i++) {
//当前坐标向上右下左走
int a=poll[0]+dx[i],b=poll[1]+dy[i];
//边界判断||已经访问-----> 跳过这个格子
if(a<0 || a>=row|| b<0 ||b>=col ||array[a][b]=='#') {
continue;
}
//否则 符合
array[a][b]='#';
queue.offer(new int[] {a,b});
}
}
return res;
}
}
DFS 深度优先遍历
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
public class Acwing_1113_红与黑 {
//BFS 宽度优先遍历
static int row,col,res;
static char[][] array=new char[25][25];
//上 右 下 左
static int[] dx= {-1,0,1,0};
static int[] dy= {0,1,0,-1};
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
while(true) {
// 输入列行 空格隔开
String[] str1 = br.readLine().split(" ");
col=Integer.parseInt(str1[0]);
row=Integer.parseInt(str1[1]);
//最后输入0 0 结束输出
if(col==0&&row==0) break;
//初始化数组array,并找到当前坐标@
int x=0,y=0;
for(int i=0;i<row;i++) {
//输入一行 没有空格
String str2 = br.readLine();
for(int j=0;j<col;j++) {
array[i][j]=str2.charAt(j);
if(array[i][j]=='@') {
x=i;y=j;
}
}
}
System.out.println(dfs(x,y));
}
}
public static int dfs(int x,int y) {
int res=1;
array[x][y]='#';
for(int i=0;i<4;i++) {
int a=x+dx[i],b=y+dy[i];
if(a>=0 && a<row && b>=0 && b<col &&array[a][b]=='.') {
res+=dfs(a,b);
}
}
return res;
}
}