思想
附加特殊行走规则的两次bfs。
代码
import java.io.*;
import java.util.Arrays;
public class Main{
static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
static PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
static int N = 1010, M = (int)1e6+5, INF = 0x3f3f3f3f, n, m;
static int[][] d = new int[N][N]; //d[i][j]表示从(x1, y1)到(i, j)需要的最小能量
static int[][] dir = new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
static char[][] g;
public static void bfs(int A, int B, int[][] dis){
for(int i=0; i<N; i++) Arrays.fill(dis[i], INF);
dis[A][B] = 0;
PII[] q = new PII[M];
int tt=-1, hh=0;
q[++tt] = new PII(A, B);
while(hh<=tt){
PII t = q[hh++];
int x = t.x, y = t.y;
for(int i=0; i<4; i++){
int tox = x+dir[i][0], toy = y+dir[i][1];
if(tox<0 || tox>=n || toy<0 || toy>=m) continue;
if(dis[tox][toy] != INF) continue;
//行走规则
if(g[tox][toy] == (g[x][y]+1-'A')%4+'A'){
dis[tox][toy] = dis[x][y] + 1;
q[++tt] = new PII(tox, toy);
}
}
}
}
public static void main(String[] args)throws IOException{
String[] input = in.readLine().split(" ");
n = Integer.parseInt(input[0]); m = Integer.parseInt(input[1]);
input = in.readLine().split(" ");
int A = Integer.parseInt(input[0])-1, B = Integer.parseInt(input[1])-1, C = Integer.parseInt(input[2])-1, D = Integer.parseInt(input[3])-1;
g = new char[n][m];
for(int i=0; i<n; i++) g[i] = in.readLine().toCharArray();
bfs(A, B, d);
int res = d[C][D];
out.println(res==INF?"No":"Yes");
out.flush();
out.close();
}
}
class PII{
int x, y;
public PII(int x, int y){
this.x = x;
this.y = y;
}
}