算法分析

双端队列

解决问题：
双端队列主要解决图中边的权值只有0或者1的最短路问题

操作：
每次从队头取出元素，并进行拓展其他元素时

• 1、若拓展某一元素的边权是0，则将该元素插入到队头
• 2、若拓展某一元素的边权是1，则将该元素插入到队尾

与堆优化Dijkstra 一样，必须在出队时才知道每个点最终的最小值，而和一般的bfs不一样，原因是如下图所示

回归到题目

首先明确的一点是，这里是图中的格子和点是不一样的，点是格子上的角角上的点，每个点都有4个方向可以走，分别对应的是左上角，右上角，右下角，左下角，

踩过格子到达想去的点时，需要判断是否需要旋转电线，若旋转电线表示从 当前点 到 想去的点 的边权是1，若不旋转电线则边权是0

按左上角，右上角，右下角，左下角遍历的顺序

• 1、dx[]和dy[]表示可以去其他点的方向
• 2、id[]和iy[]表示需要踩某个方向的各种才能去到相应的点
• 3、cs[]表示当前点走到4个方向的点理想状态下格子形状(边权是0的状态)

时间复杂度 $O(nm)$

参考文献

算法提高课

Java 代码

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

public class Main {

    static char[] cs = new char[] {'\\', '/', '\\', '/'};//'/'需要转义
    static int[] dx = new int[]{-1, -1, 1, 1};
    static int[] dy = new int[]{-1, 1, 1, -1};
    static int[] ix = new int[]{-1, -1, 0, 0};
    static int[] iy = new int[]{-1, 0, 0, -1};
    static int N = 501, INF = 0x3f3f3f3f;
    static int n, m;
    static char[][] g = new char[N][N];
    static boolean[][] st = new boolean[N][N];
    static int[][] dist = new int[N][N];
    static int bfs()
    {
        for(int i = 0;i <= n;i ++) Arrays.fill(st[i], false);
        for(int i = 0;i <= n;i ++) Arrays.fill(dist[i], INF);
        dist[0][0] = 0;
        Deque<PII> q = new LinkedList<PII>();
        q.addLast(new PII(0, 0));
        while(!q.isEmpty())
        {
            PII t = q.pollFirst();
            int x = t.x, y = t.y;
            if (x == n && y == m) return dist[x][y] ;
            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] == cs[i] ? 0 : 1;//观察是否需要转动，若处于理想状态则权值是0，否则需要旋转1次权值是1
                int d = dist[x][y] + w;
                if(d < dist[a][b])
                {
                    dist[a][b] = d;
                    if(w == 1) q.addLast(new PII(a, b));
                    else q.addFirst(new PII(a, b));
                }
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int T = scan.nextInt();
        while(T -- > 0)
        {
            n = scan.nextInt();
            m = scan.nextInt();
            for(int i = 0;i < n;i ++) 
            {
                String s = scan.next();
                for(int j = 0;j < m;j ++)
                    g[i][j] = s.charAt(j);
            }

            //n + m不是偶数表示无解
            if(((n + m) & 1) != 0) System.out.println("NO SOLUTION");
            else System.out.println(bfs());
        }
    }
}
class PII
{
    int x, y;
    PII(int x, int y)
    {
        this.x = x;
        this.y = y;
    }
}