BFS
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {
static int N;
static char[][] map;
static int[] dx = { -1, 0, 1, 0 };
static int[] dy = { 0, -1, 0, 1 };
static int ans;
static boolean[][] vis;
class pair {
int x;
int y;
int step;
int flag;// 2是起点之后,1是+,2是-,不要这个变量也行
public pair(int x, int y, int step, int flag) {
this.x = x;
this.y = y;
this.step = step;
this.flag = flag;
}
}
static void bfs(int x, int y) {
Main main = new Main();
Queue<pair> queue = new LinkedList<pair>();
queue.add(main.new pair(x, y, 0, 2));
vis[x][y] = true;
while (!queue.isEmpty()) {
pair newPair = queue.poll();
for (int i = 0; i < 4; i++) {
int newX = newPair.x + dx[i];
int newY = newPair.y + dy[i];
if (newX >= 0 && newX < N && newY >= 0 && newY < N &&vis[newX][newY]==false) {
if(map[newX][newY]=='B') {
ans = Math.min(ans,newPair.step+1);
}
if ((newPair.flag == 2 || newPair.flag == 1) && map[newX][newY] == '-') {
queue.add(main.new pair(newX, newY, newPair.step + 1, 0));
vis[newX][newY] = true;
}
if ((newPair.flag == 2 || newPair.flag == 0) && map[newX][newY] == '+') {
queue.add(main.new pair(newX, newY, newPair.step + 1, 1));
vis[newX][newY] = true;
}
}
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
map = new char[N + 1][N + 1];
vis = new boolean[N + 1][N + 1];
int startX = 0,startY = 0;
for (int i = 0; i < N; i++) {
String[] str = br.readLine().split(" ");
for (int j = 0; j < N; j++) {
map[i][j] = str[j].charAt(0);
if (map[i][j] == 'A') {
startX = i;
startY = j;
}
}
}
ans = Integer.MAX_VALUE;
bfs(startX,startY);
if(ans==Integer.MAX_VALUE)ans=-1;
System.out.println(ans);
}
}