天天看點

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

}

}