题目描述
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。
你站在其中一块黑色的瓷砖上,只能向相邻(上下左右四个方向)的黑色瓷砖移动。
请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
Java – BFS
import java.util.Scanner;
import java.util.Queue;
import java.util.LinkedList;
class Main{
static final int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static int n = 0, m = 0;
static int res = 0;
static char[][] a = new char[25][25];
static int x = 0, y = 0;
public static void main(String[] args){
Scanner s = new Scanner(System.in);
while (true){
String index = s.nextLine();
String[] in = index.split(" ");
n = Integer.parseInt(in[0]);
m = Integer.parseInt(in[1]);
if(n == 0 && m == 0) break;
x = 0;
y = 0;
for(int i = 0; i < m; i ++){
String line = s.nextLine();
for(int j = 0; j < n; j ++){
a[i][j] = line.charAt(j);
if(a[i][j] == '@'){
x = i;
y = j;
}
}
}
System.out.println(bfs(x, y));
}
}
public static int bfs(int x, int y){
res = 0;
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{x,y});
a[x][y] = '#';
while(!q.isEmpty()){
int[] cor = q.poll();
res ++;
for(int i = 0; i < 4; i++){
int f = cor[0] + dx[i];
int s = cor[1] + dy[i];
if(f < 0 || f >= m || s < 0 || s >= n || a[f][s] != '.') continue;
a[f][s] = '#';
q.offer(new int[]{f,s});
}
}
return res;
}
}
Java - DFS
import java.util.Scanner;
class Main{
static final int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};
static int col = 0, row = 0;
static int res = 0;
static char[][] a = new char[25][25];
static int x = 0, y = 0;
public static void main(String[] args){
Scanner s = new Scanner(System.in);
while (true){
String index = s.nextLine();
String[] in = index.split(" ");
col = Integer.parseInt(in[0]);
row = Integer.parseInt(in[1]);
if(col == 0 && row == 0) break;
x = 0;
y = 0;
for(int i = 0; i < row; i ++){
String line = s.nextLine();
for(int j = 0; j < col; j ++){
a[i][j] = line.charAt(j);
if(a[i][j] == '@'){
x = i;
y = j;
}
}
}
System.out.println(dfs(x, y));
}
}
public static int dfs(int x, int y){
res = 1;
a[x][y] = '#';
for(int i = 0; i < 4; i ++){
int r = x + dx[i], s = y + dy[i];
if(r >= 0 && r < row && s >= 0 && s < col && a[r][s] == '.'){
a[r][s] = '#';
res += dfs(r,s);
}
}
return res;
}
}