AcWing 1113. 红与黑——Java宽搜版代码
原题链接
简单
作者:
yqh
,
2021-01-18 17:04:22
,
所有人可见
,
阅读 407
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
String[] temp = reader.readLine().split(" ");
ArrayList<Integer> result = new ArrayList<>();
class Pair{
int x;
int y;
public Pair(int x, int y) {
this.x = x;
this.y = y;
}
}
while(true){
int w = Integer.parseInt(temp[0]), h = Integer.parseInt(temp[1]);
//这里为方便边界处理,多声明一圈的区域
/*
例: 0表示不使用的空间,*表示实际使用的空间,当前需要使用2x3的区域
0 0 0 0 0
0 * * * 0
0 * * * 0
0 0 0 0 0
*/
int[][] flag = new int[h+2][w+2];
char[][] in = new char[h+2][w+2];
int x = 0, y = 0, num = 1;
for (int i = 1; i <= h; i++) {
char[] tmp = reader.readLine().toCharArray();
for (int j = 1; j <= w; j++) {
in[i][j] = tmp[j-1];
if (tmp[j-1] == '@'){
x = i;y = j;
}
}
}
int[] xi = {0,0,-1,1}, yi = {1,-1,0,0};
Deque<Pair> queue = new ArrayDeque<>(h*w*2);
flag[x][y] = 1;
queue.addLast(new Pair(x,y));
while(!queue.isEmpty()){
Pair p = queue.pollFirst();
for (int i = 0; i < 4; i++) {
//如果当前位置还没有走过,或者当前位置可以走(越界部分未初始化,也属于不能走的位置)
if ((flag[p.x+xi[i]][p.y+yi[i]] != 1) && (in[p.x+xi[i]][p.y+yi[i]] == '.')){
queue.addLast(new Pair(p.x+xi[i],p.y+yi[i]));
num++;
}
//不管当前位置能不能走,都将其标记为已走过
flag[p.x+xi[i]][p.y+yi[i]] = 1;
}
}
result.add(num);
temp = reader.readLine().split(" ");
if (temp[0].equals("0")){
break;
}
}
for (int i = 0; i < result.size(); i++) {
writer.write(result.get(i) +"\n");
}
writer.flush();
}
}