$$\color{Red}{电路维修—双端队列模型}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

思路

无负权图的做法，往往都是由Dijkstra算法推广而来。

这道题我们可以抽象成一个图，而边并不是以当前状态而定，而是由如果前往的节点的斜线，不需要旋转，边权看作0，而需要选择才能走过去，看作1。

其实能观察出一个这道题的性质：一个点的横坐标和纵坐标之和，如果为奇数，一定无法到达。

理由： 起点是偶数点（0，0） ——》 0

而位移每次都是横纵坐标都进行变化1个单位。故只能到达偶数和的点。可以优化剪枝。

其次这道题我们移动其实是在图的端点，而我们实际获得的图是按字符来算的，故我们需要进行坐标的映射转换。

这道题的难点不在于 dx [] dy []这两个数组，和以前我们处理偏移量没什么区别。

难点在于：如何把我们移动后会经过哪个字符位置？

直接举例推断：下面 <>括号内部是端点坐标，而（）括号内部是字符端点坐标。

我们假设我们当前端点位置是 <1,1>

我们能够移动到 <0,2> <2,2> <2,0> <0,0>

而我们会经过 (0,1) (1,1) (1,0) (0,0)字符位置的斜线

即我们获取端点<1,1>对应这四种移动会到达字符位置的偏移量应该是 -> (-1,0) (0,0) (0,-1) (-1,-1)

<0,0>  <0,1>  <0,2>  <0,3>
-------------------------
| (0,0) | (0,1) | (0,2) |
-------------------------
<1,0>  <1,1>  <1,2>  <1,3>
-------------------------
| (1,0) | (1,1) | (1,2) |
-------------------------
<2,0>  <2,1>  <2,2>  <2,3>
-------------------------
| (2,0) | (2,1) | (2,2) |
-------------------------

那么我们由此可以进行bfs，而之前我们只需要普通队列，这道题需要用双端队列的原因是：

以前我们更新的点距离都势必满足大于当前节点，满足单调性和分堆性。

| (d=0) (d=0) (d=0) -----  | (d=1) (d=1) ---- | (d=2) (d=2) ---- | ----------- 

而这道题如果还用普通队列更新的方式，势必会打破局部单调性。

为了满足单调性，就采取双端队列的更新方式：为 0 放队头， 为 1 放队尾

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {
    static int N = 510, n, m, T;
    //端点的偏移量数组
    static int[] dx = {-1, 1, 1, -1}, dy = {1, 1, -1, -1};
    //格点对应端点位移后的偏移
    static int[] ix = {-1, 0, 0, -1}, iy = {0, 0, -1, -1};
    //对应偏移量移动无花费的格子状态
    static char[] chars = {'/', '\\', '/', '\\'};
    static char[][] g = new char[N][N];
    static int[][] d = new int[N][N];
    static boolean[][] st = new boolean[N][N];

    static class Node {
        int x, y;

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }

    public static int bfs() {
        for (int i = 0; i <= n; i++) Arrays.fill(st[i], false);
        for (int i = 0; i <= n; i++) Arrays.fill(d[i], 0x3f3f3f3f);
        d[0][0] = 0;
        LinkedList<Node> q = new LinkedList<Node>();
        q.add(new Node(0, 0));
        while (!q.isEmpty()) {
            Node node = q.pop();
            int x = node.x;
            int y = node.y;
            if (x == n && y == m) return d[n][m];
            if (st[x][y]) continue;
            st[x][y] = true;

            for (int i = 0; i < 4; i++) {
                int a = x + dx[i], b = y + dy[i];
                if (a < 0 || a > n || b < 0 || b > m) continue;
                int ga = x + ix[i], gb = y + iy[i];
                int w = g[ga][gb] == chars[i] ? 0 : 1;
                int dist = d[x][y] + w;
                if (dist < d[a][b]){
                    d[a][b] = dist;
                    if (w == 1) q.addLast(new Node(a, b));
                    else q.addFirst(new Node(a, b));
                }
            }
        }
        return -1;
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        T = Integer.parseInt(br.readLine());
        while (T-- > 0) {
            String[] s1 = br.readLine().split(" ");
            n = Integer.parseInt(s1[0]);
            m = Integer.parseInt(s1[1]);
            for (int i = 0; i < n; i++) {
                String s2 = br.readLine();
                for (int j = 0; j < m; j++) g[i][j] = s2.charAt(j);
            }
            if ((n + m & 1) != 0) System.out.println("NO SOLUTION");
            else System.out.println(bfs());
        }
    }
}