题解 | #迷宫#

求下列情况距离的最小值（如果合法）

S不经过D直接走到E bfs(S,E)

S先拿钥匙 bfs(S,E) 再从钥匙处走到E bfs(K,E)

bfs最好复用。

import java.io.*;
import java.util.*;
import java.math.*;

public class Main {
    public static int H, W, S, E, K, D;
    public static char[][] mg;
    public static int[] dis;
    public static boolean[] v;
    public static boolean key = false;
    public static int[][] dir = {{-1,0},{1,0},{0,-1},{0,1}};
    public static boolean bfs(int s, int t) {//s为起点，t为终点
        Queue<Integer> q = new LinkedList<>();
        q.add(s);
      //这里不用dis[s] = 0 可以接上次bfs一直累加
        v[s] = true;
        while(!q.isEmpty()) {
            int tmp = q.poll();
            int x = tmp / W, y = tmp % W;
            for(int i = 0; i < 4; ++i) {
                int nx = x + dir[i][0], ny = y + dir[i][1], pos = nx * W + ny;
                //1、四周是墙壁无需判断越界 2、如果下个方向D但起点不是K，视为墙壁
                if(mg[nx][ny] == 'W' || v[pos] || mg[nx][ny] == 'D' && s != K) continue;
                dis[pos] = dis[tmp] + 1;
                v[pos] = true;
                if(pos == t) return true;
                q.add(pos);
            }
        }
        return false;
    }

	public static void main(String[] args) {
		InputReader in = new InputReader();
		PrintWriter out = new PrintWriter(System.out);
        H = in.nextInt();
        W = in.nextInt();
        mg = new char[H][W];
        dis = new int[H * W];
        v = new boolean[H * W];
        for(int i = 0; i < H; ++i) {
            char[] chs = in.next().toCharArray();
            for(int j = 0; j < W; ++j) {
                mg[i][j] = chs[j];
                if(mg[i][j] == 'S') S = i * W + j;
                if(mg[i][j] == 'E') E = i * W + j;
                if(mg[i][j] == 'K') K = i * W + j;
            }
        }
        int ans = Integer.MAX_VALUE;//假设距离无限远
        if(bfs(S, E)) ans = dis[E];//不经过D直接走到E
        for(int i = 0, l = H * W; i < l; ++i) v[i] = false;//每次bfs前都要把标记清除掉
        if(bfs(S, K)) {//能拿到钥匙
            for(int i = 0, l = H * W; i < l; ++i) v[i] = false;
            if(bfs(K, E)) ans = Math.min(ans, dis[E]);//取二者最小值
        }
        out.println(ans == Integer.MAX_VALUE ? -1 : ans);
		out.close();
	}
}
class InputReader{BufferedReader buf;StringTokenizer tok;InputReader(){buf = new BufferedReader(new InputStreamReader(System.in));}boolean hasNext(){while (tok == null || !tok.hasMoreElements()){try{tok = new StringTokenizer(buf.readLine());}catch (Exception e){return false;}}return true;}String next(){if (hasNext())
			return tok.nextToken();return null;}int nextInt(){return Integer.parseInt(next());}long nextLong(){return Long.parseLong(next());}double nextDouble(){return Double.parseDouble(next());}BigInteger nextBigInteger(){return new BigInteger(next());}BigDecimal nextBigDecimal(){return new BigDecimal(next());}}