题目描述
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
输入格式
输入包括多个数据集合。
每个数据集合的第一行是两个整数 W 和 H,分别表示 x 方向和 y 方向瓷砖的数量。
在接下来的 H 行中,每行包括 W 个字符。每个字符表示一块瓷砖的颜色,规则如下
1)‘.’:黑色的瓷砖;
2)‘#’:白色的瓷砖;
3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。
当在一行中读入的是两个零时,表示输入结束。
输出格式
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
数据范围
1≤W,H≤20
输入样例:
6 9
....#.
.....#
......
......
......
......
......
#@...#
.#..#.
0 0
输出样例:
45
注意:本题会有多个测试集,所以要加上while循环,遇到 0 ,0时在跳出循环
BFS 宽度优先搜索
/*BFS 宽度优先搜索*/
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.LinkedList;
public class Main{
static int row,col,res;
static char[][] g = new char[25][25];
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
static Queue<int[]> q = 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]);
if(col == 0 && row == 0) break;
int x = 0, y = 0; //初始化数组g,并找到当前坐标
for(int i = 0; i < row; i ++){
String str2 = br.readLine();
for(int j = 0; j < col; j ++){
g[i][j] = str2.charAt(j);
if(g[i][j] == '@'){
x = i ; y = j;
}
}
}
System.out.println(bfs(x,y)); //注意要加上ln,因为会有多个测试集
}
}
private static int bfs(int x, int y){
q.offer(new int[]{x,y}); //把当前坐标加入到队列中
res = 0;
g[x][y] = '#'; //当前坐标设置为'#',表示已经走过了
while(q.size() != 0){
int[] poll = q.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 ||g[a][b] != '.') continue;
g[a][b] = '#';
q.offer(new int[]{a,b});
}
}
return res;
}
}
DFS 深度优先搜索
/*DFS 深度优先搜索,用递归实现的*/
import java.io.*;
public class Main{
static int N = 25, row, col;
static char[][] g = new char[N][N];
static int[] dx = {-1,0,1,0};
static int[] dy = {0,1,0,-1};
public static void main(String[] args) throws Exception{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
//因为后面还有两个00需要读,所以加上了这个,只会读取两次,一次69,一次00,然后break;
while(true){
String[] ss = read.readLine().split(" ");
row = Integer.parseInt(ss[1]);
col = Integer.parseInt(ss[0]);
if(row == 0 && col == 0) break; //读到00就结束
//初始化数组g[]
int x = 0, y = 0;
for(int i = 0; i < row; i++){
String s = read.readLine();
for(int j = 0; j < col; j++){
g[i][j] = s.charAt(j);
if(g[i][j] == '@'){
x = i; y = j;
}
}
}
System.out.println(dfs(x, y)); //注意加上ln,因为有多个测试集
}
}
public static int dfs(int x, int y){
int res = 1;
g[x][y] = '#'; //把当前值改为'#',用来预防重复走
for(int i = 0; i < 4; i++){
int a = x + dx[i], b = y + dy[i]; //代表当前点向上右下左走
//如果在数组的范围内并且没有遇见重复的,res + 1 递归
if(a >= 0 && a<row && b>=0 && b<col && g[a][b]=='.') res += dfs(a, b);
}
return res;
}
}