采用广度优先遍历逐层遍历:
- 找到@所在位置,当作根节点
- 每次访问一个结点后,将该结点入栈,然后将对应位置状态设为“*”(防止重复访问)
- 从栈中取出上一轮的结点,依次将上下左右入栈
- 直到栈为空
import java.util.Scanner;
import java.util.Stack;
class Position{
int row;
int col;
public Position(int row, int col) {
this.row = row;
this.col = col;
}
}
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while (true) {
int w = scanner.nextInt();
int h = scanner.nextInt();
if(w == 0 && h == 0){
break;
}
scanner.nextLine();
int count = 0;
char[][] arr = new char[h][w];
for (int i = 0; i < h; i++) {
String line = scanner.nextLine().replaceAll(" ", "");
arr[i] = line.toCharArray();
}
Stack<Position> stack = new Stack<>();
for (int i = 0; i < h; i++) {
for (int j = 0; j < w; j++) {
if (arr[i][j] == '@') {
stack.push(new Position(i, j));
arr[i][j] = '*';
}
}
}
while (!stack.isEmpty()) {
//访问p
Position p = stack.pop();
int row = p.row;
int col = p.col;
count++;
//改变访问点的状态
if (row > 0 && arr[row - 1][col] == '.') {
stack.push(new Position(row - 1, col));
arr[row-1][col] = '*';
}
if (row + 1 < h && arr[row + 1][col] == '.') {
stack.push(new Position(row + 1, col));
arr[row+1][col] = '*';
}
if (col > 0 && arr[row][col - 1] == '.') {
stack.push(new Position(row, col - 1));
arr[row][col-1] = '*';
}
if (col + 1 < w && arr[row][col + 1] == '.') {
stack.push(new Position(row, col + 1));
arr[row][col+1] = '*';
}
}
System.out.println(count);
}
}
}
```