JavaBFS求调教 52分
查看原帖
JavaBFS求调教 52分
585302
feishia6楼主2023/5/17 17:35
import java.io.*;
import java.math.*;
import java.util.*;

public class Main {
    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static int[] dx = {0, 1, -1, 0, 0};
    static int[] dy = {0, 0, 0, 1, -1};
    public static void main(String[] args) throws IOException {
        Scanner sc=new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        char[][] a = new char[n + 1][m + 1];
        int sx = 0, sy = 0;
        for (int i = 1; i <= n; i++) {
            String t = sc.next();
            for (int j = 1; j <= m; j++) {
                a[i][j] = t.charAt(j - 1);
                if (a[i][j] == '@') {
                    sx = i;
                    sy = j;
                }
            }
        }
        Map<Integer, List<Node>> map = new HashMap<>();
        init(map, n, m, a);
        boolean[][] f = new boolean[n + 1][m + 1];
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(sx, sy, 0));
        f[sx][sy] = true;
        while (!q.isEmpty()) {
            Node t = q.poll();
            int x = t.x;
            int y = t.y;
            int step = t.step;
            if (a[x][y] == '=') {
                out.println(step);
                break;
            }
            boolean con = false;
            if (map.containsKey(x * 300 + y)) {
                List<Node> nd = map.get(x * 300 + y);
                for (Node p : nd) {
                    if (!f[p.x][p.y]) {
                        f[p.x][p.y] = true;
                        q.offer(new Node(p.x, p.y, step));
                        con = true;
                    }
                }
            }
            if (con) continue;
            for (int i = 1; i <= 4; i++) {
                int xx = dx[i] + x;
                int yy = dy[i] + y;
                if (xx >= 1 && yy >= 1 && xx <= n && yy <= m && !f[xx][yy] && a[xx][yy] != '#') {
                    q.offer(new Node(xx, yy, step + 1));
                    f[xx][yy] = true;
                }
            }
        }
        out.flush();
        out.close();
    }
    static void init(Map<Integer, List<Node>> map, int n, int m, char[][] a) {
        Map<Character, List<Node>> tmp = new HashMap<>();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] >= 'A' && a[i][j] <= 'Z') {
                    if (!tmp.containsKey(a[i][j])) {
                        tmp.put(a[i][j], new ArrayList<>());
                    }
                    tmp.get(a[i][j]).add(new Node(i, j, -999));
                }
            }
        }
        for (char c : tmp.keySet()) {
            List<Node> t = tmp.get(c);
            Node l = t.get(0);
            Node r = t.get(1);
            int x1 = l.x;
            int y1 = l.y;
            int x2 = r.x;
            int y2 = r.y;
            if (!map.containsKey(x1 * 300 + y1)) {
                map.put(x1 * 300 + y1, new ArrayList<>());
            }
            if (!map.containsKey(x2 * 300 + y2)) {
                map.put(x2 * 300 + y2, new ArrayList<>());
            }
            map.get(x1 * 300 + y1).add(new Node(x2, y2, -999));
            map.get(x2 * 300 + y2).add(new Node(x1, y1, -999));
        }
    }
    static class Node {
        int x, y, step;

        public Node(int x, int y, int step) {
            this.x = x;
            this.y = y;
            this.step = step;
        }
    }
}
2023/5/17 17:35
加载中...