P1746 离开中山路 JAVA题解 （广搜和双向广搜优化）

题目背景

《爱与愁的故事第三弹·shopping》最终章。

题目描述

爱与愁大神买完东西后，打算坐车离开中山路。现在爱与愁大神在 x1,y1x1​,y1​ 处，车站在 x2,y2x2​,y2​ 处。现在给出一个 n×n(n≤1000)n×n(n≤1000) 的地图，00 表示马路，11 表示店铺（不能从店铺穿过），爱与愁大神只能垂直或水平着在马路上行进。爱与愁大神为了节省时间，他要求最短到达目的地距离（每两个相邻坐标间距离为 11）。你能帮他解决吗？

输入格式

第 11 行包含一个数 nn。

第 22 行到第 n+1n+1 行：整个地图描述（00 表示马路，11 表示店铺，注意两个数之间没有空格）。

第 n+2n+2 行：四个数 x1,y1,x2,y2x1​,y1​,x2​,y2​。

输出格式

只有 11 行，即最短到达目的地距离。

输入输出样例

输入 #1复制

3
001
101
100
1 1 3 3

输出 #1复制

4

说明/提示

对于 20%20% 数据，满足 1≤n≤1001≤n≤100。

对于 100%100% 数据，满足 1≤n≤10001≤n≤1000。

单向广搜

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[][] div = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int n;
    static int[][] arr, span;

    static class Pair {
        int x;
        int y;

        Pair(int a, int b) {
            x = a;
            y = b;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n+1][n+1];
        span = new int[n+1][n+1];
        sc.nextLine();
        for (int i = 1; i <= n; i++) {
            String s = sc.nextLine();
            for (int j = 1; j <= n; j++) {
                arr[i][j] = s.charAt(j-1) - '0';
                span[i][j] = -1;
            }
        }
        int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt();
        System.out.println(bfs(x1 , y1 , x2 , y2 ));
    }

    private static int bfs(int x1, int y1, int x2, int y2) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(x1, y1));
        span[x1][y1] = 0;
        while (!queue.isEmpty()) {
            Pair poll = queue.poll();
            for (int i = 0; i < div.length; i++) {
                int xx = div[i][0] + poll.x;
                int yy = div[i][1] + poll.y;
                if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && arr[xx][yy] == 0 && span[xx][yy] == -1) {
                    span[xx][yy]=span[poll.x][poll.y]+1;
                    if (xx==x2&&yy==y2) {
                        return span[xx][yy];
                    }
                    queue.add(new Pair(xx,yy));
                }
            }
        }
        return span[x2][y2];
    }
}

双向广搜

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int[][] div = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    static int n;
    static int[][] arr, span;

    static class Pair {
        int x;
        int y;

        Pair(int a, int b) {
            x = a;
            y = b;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n+1][n+1];
        span = new int[n+1][n+1];
        sc.nextLine();
        for (int i = 1; i <= n; i++) {
            String s = sc.nextLine();
            for (int j = 1; j <= n; j++) {
                arr[i][j] = s.charAt(j-1) - '0';
                span[i][j] = -1;
            }
        }
        int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt();
        System.out.println(bfs(x1 , y1 , x2 , y2 ));
    }

    private static int bfs(int x1, int y1, int x2, int y2) {
        Queue<Pair> queue = new LinkedList<>();
        queue.add(new Pair(x1, y1));
        queue.add(new Pair(x2,y2));
        span[x1][y1] = 0;
        arr[x1][y1]=2;
        span[x2][y2]=0;
        arr[x2][y2]=3;
        while (!queue.isEmpty()) {
            Pair poll = queue.poll();
            for (int i = 0; i < div.length; i++) {
                int xx = div[i][0] + poll.x;
                int yy = div[i][1] + poll.y;
                if (xx >= 1 && xx <= n && yy >= 1 && yy <= n &&arr[xx][yy]+arr[poll.x][poll.y]==5) {
                    return span[xx][yy]+span[poll.x][poll.y]+1;
                }
                if (xx >= 1 && xx <= n && yy >= 1 && yy <= n && arr[xx][yy] == 0) {
                    span[xx][yy]=span[poll.x][poll.y]+1;
                    arr[xx][yy]=arr[poll.x][poll.y];
                    queue.add(new Pair(xx,yy));
                }
            }
        }
        return -1;
    }
}

两个的运行结果，对比一下虽然没快多少，但双向广搜还是要快一些