牛客小白月赛75-D-矩阵

题目描述

现有一个大小为 n × m的二维矩阵，每个元素 s_{i,j}可能是字符 0, 1。
阿宁一开始站在 (1,1)，目标走到 (n,m)。
假设当前在 (x,y) 一个相邻的位置 (x',y')，上下左右相邻。可以进行一下其中一个行为，花费一个单位时间：

1. 如果 s_{x,y}是0， s_{x ^\prime,y'}是1，可以从(x,y) 走到(x',y')。

2. 如果 s_{x,y}是1，s_{x ^\prime,y'}是0，可以从(x,y) 走到(x',y')。

3. 将 s_{x,y}变成1。

4. 将 s_{x,y}变成0。

问阿宁从 (1,1)走到 (n,m)需要最少多少单位时间？

输入描述

第一行输入两个正整数 n, m。
接下来输入 n 行，每行 m个字符，字符仅包含 0、 1。
1 \le n，m \le 10^3

输出描述

输出一个整数。

题解

简单BFS。其中点到起点的距离的存储方式需要稍作改变，需要存储点处于两种状态时到起点的最小距离。同样地，在将点放入优先队列时需要记录该点的状态。更新最小距离时使用松弛思想。

import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static final int[] dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
    private static class Point implements Comparable<Point>{
        public int x;
        public int y;
        public int status;  //该点状态，0或1
        public int distance;  //该点距离起点的距离

        public Point(int x, int y, int status, int distance) {
            this.x = x;
            this.y = y;
            this.status = status;
            this.distance = distance;
        }

        @Override
        public int compareTo(Point o) {
            return Integer.compare(this.distance, o.distance);
        }
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] map = new int[1010][1010];
        for (int i = 1; i <= n; i ++) {
            String s = scanner.next();
            for (int j = 1; j <= m; j ++) {
                map[i][j] = Integer.parseInt(String.valueOf(s.charAt(j - 1)));
            }
        }
        int[][][] dis = new int[n + 1][m + 1][2];  //点(x,y)处于状态0或1时距离起点的距离
        for (int i = 1; i <= n; i ++) {
            for (int j = 1; j <= m; j ++) {
                dis[i][j] = new int[]{Integer.MAX_VALUE, Integer.MAX_VALUE};
            }
        }
        dis[1][1][map[1][1]] = 0;  //起点距离为0
        Queue<Point> queue = new PriorityQueue<>();
        queue.add(new Point(1, 1, map[1][1], 0));
        while (!queue.isEmpty()) {
            Point point = queue.poll();
            for (int i = 0; i < 4; i ++) {
                int nextX = point.x + dx[i], nextY = point.y + dy[i];
                if (nextX >= 1 && nextX <= n && nextY >= 1 && nextY <= m) {
                    int nextStatus = map[nextX][nextY];
                    if (nextStatus != point.status) {  //相邻点的状态不同
                        int newDistance = point.distance + 1;
                        if (newDistance < dis[nextX][nextY][nextStatus]) {  //松弛
                            dis[nextX][nextY][nextStatus] = newDistance;
                            queue.add(new Point(nextX, nextY, nextStatus, newDistance));
                        }
                    }
                    else {  //相邻点的状态相同
                        int newDistance = point.distance + 2;
                        int newStatus = 1 - nextStatus;
                        if (newDistance < dis[nextX][nextY][newStatus]) {
                            dis[nextX][nextY][newStatus] = newDistance;
                            queue.add(new Point(nextX, nextY, newStatus, newDistance));
                        }
                    }
                }
            }
        }
        System.out.println(Math.min(dis[n][m][0], dis[n][m][1]));
    }
}