题目描述
与BFS走迷宫的思路相反。
代码
import java.io.*;
import java.util.Queue;
import java.util.LinkedList;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static char[][] g;
static Queue<node> q = new LinkedList<>();
static int[][] dir = new int[][]{{-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, 0}, {1, -1}, {0, -1}, {-1, -1}}; //因为斜着放的路障也可以阻隔一条路,所以这里要有8个方向
static int n;
//为墙边的路障标号上:1,右:2,下:3,左:4,并加入队列
public static void init(){
for(int i=0; i<n; i++){
if(g[0][i]=='X'){g[0][i] = '1'; q.add(new node(0, i));}
if(g[i][n-1]=='X'){g[i][n-1] = '2'; q.add(new node(i, n-1));}
if(g[n-1][i]=='X'){g[n-1][i] = '3'; q.add(new node(n-1, i));}
if(g[i][0]=='X'){g[i][0] = '4'; q.add(new node(i, 0));}
}
}
//判断放一个路障是否形成阻隔
public static boolean check(int x, int y, char tag){
for(int i=0; i<8; i++){
int tox = x+dir[i][0], toy = y+dir[i][1];
//走过边界就判断是否已经形成阻隔
if(tox<0 || toy>=n){
if(tag=='4' || tag=='3') return true;
}else if(tox>=n || toy<0){
if(tag=='1' || tag=='2') return true;
}else{
//没走过边界,遇到别的路障判断是否形成阻隔
char totag = g[tox][toy];
if((tag=='1' || tag=='2')&&(totag=='3' || totag=='4')) return true;
else if((tag=='3' || tag=='4')&&(totag=='1' || totag=='2')) return true;
}
}
return false;
}
public static int bfs(){
int ans = 2;
while(!q.isEmpty()){
node t = q.poll();
for(int i=0; i<8; i++){
int tox = t.x+dir[i][0], toy = t.y+dir[i][1];
char tag = g[t.x][t.y]; //存储当前的阻隔编号
//放一个路障的情况:如果没有走出边界,就判断再走一步是否形成阻隔
if(tox>=0 && tox<n && toy>=0 && toy<n) ans = check(tox, toy, tag)?1:ans;
//不用放路障的情况:
//走过边界就判断是否已经形成阻隔
if(tox<0 || toy>=n){
if(tag=='4' || tag=='3') return 0;
}else if(tox>=n || toy<0){
if(tag=='1' || tag=='2') return 0;
}else{
char totag = g[tox][toy];
//遇到别的路障判断是否形成阻隔
if((tag=='1' || tag=='2')&&(totag=='3' || totag=='4')) return 0;
else if((tag=='3' || tag=='4')&&(totag=='1' || totag=='2')) return 0;
//遇到路障但没形成阻隔就加入队列继续搜索
else if(totag=='X'){g[tox][toy] = tag; q.add(new node(tox, toy));}
}
}
}
return ans;
}
public static void main(String[] args)throws IOException{
int T = Integer.parseInt(in.readLine());
while(T-->0){
n = Integer.parseInt(in.readLine());
q.clear();
g = new char[n][n];
for(int i=0; i<n; i++) g[i] = in.readLine().toCharArray();
init();
out.println(bfs());
}
out.flush();
out.close();
}
}
class node{
int x, y;
public node(int x, int y){
this.x = x;
this.y = y;
}
}