天天看点

java红与黑算法,AcWing 1113. 红与黑——Java宽搜版代码

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 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]);

//这里为方便边界处理,多声明一圈的区域

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 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();

}

}