题目描述

达达是来自异世界的魔女，她在漫无目的地四处漂流的时候，遇到了善良的少女翰翰，从而被收留在地球上。

翰翰的家里有一辆飞行车。

有一天飞行车的电路板突然出现了故障，导致无法启动。

电路板的整体结构是一个R行C列的网格（R,C≤500），如下图所示。

电路.png

每个格点都是电线的接点，每个格子都包含一个电子元件。

电子元件的主要部分是一个可旋转的、连接一条对角线上的两个接点的短电缆。

在旋转之后，它就可以连接另一条对角线的两个接点。

电路板左上角的接点接入直流电源，右下角的接点接入飞行车的发动装置。

达达发现因为某些元件的方向不小心发生了改变，电路板可能处于断路的状态。

她准备通过计算，旋转最少数量的元件，使电源与发动装置通过若干条短缆相连。

不过，电路的规模实在是太大了，达达并不擅长编程，希望你能够帮她解决这个问题。

注意：只能走斜向的线段，水平和竖直线段不能走。

输入格式
输入文件包含多组测试数据。

第一行包含一个整数T，表示测试数据的数目。

对于每组测试数据，第一行包含正整数R和C，表示电路板的行数和列数。

之后R行，每行C个字符，字符是”/”和”"中的一个，表示标准件的方向。

输出格式
对于每组测试数据，在单独的一行输出一个正整数，表示所需的缩小旋转次数。

如果无论怎样都不能使得电源和发动机之间连通，输出NO SOLUTION。

数据范围
1≤R,C≤500
输出样例：
1

样例

输入样例：
1
3 5
\\/\\
\\///
/\\\\
输出样例：
1

算法1

(双端队列bfs)

blablabla

时间复杂度 线性

参考文献

C++ 代码

#include<iostream>
#include<algorithm>
#include<deque>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=510;
int dist[N][N];
char g[N][N];
bool st[N][N];//一个点可能被另外多个点更新多次
int n,m;

int dir[2][4]={{-1,-1,1,1},{-1,1,1,-1}};//在这个题目中,我们走的路只能是对角线，所以坐标变化为四个对角线

//图中的每个交点看作一个结点，并且编号。同时再给每一个方格进行编号，gir数组用来计算每个节点对应的四个对角线上格子在g[N]数组的编号
int gir[2][4]={{-1,-1,0,0},{-1,0,0,-1}}; 

//这里的坐标变换要一致，我这里是从左上角开始顺时针遍历四个对角线
//转义字符要双写,这里用到了三目运算符
char op[5]="\\/\\/";

int bfs()
{
    memset(dist,0x3f,sizeof(dist));
    memset(st,0,sizeof(st));
    dist[0][0]=0;
    deque<PII> q;
    q.push_front({0,0});
    while(q.size())
    {
        auto t=q.front();//dijkstra()在出队后dist就已经确定不能改变，即可判断
        q.pop_front();
        int tx=t.x;
        int ty=t.y;
        if(tx==n&&ty==m)
        {
            return dist[n][m];
            break;
        }

        if(st[tx][ty]) continue;//判断某个点是否已经利用过；

        st[tx][ty]=true;//如果没有用过下面就要使用，标记一下

        for(int i=0;i<4;i++)//这里的顺序是按之前约定的数组，即顺时针
        {
            int nx=tx+dir[0][i];
            int ny=ty+dir[1][i];
            //计算每个点周围的四个格子(不知道为啥，格子的边界不用判断是否出界就能AC，可能是......)
            int gx=tx+gir[0][i];
            int gy=ty+gir[1][i];
            if(nx<0||ny<0||nx>n||ny>m||gx<0||gy<0||gx>=n||gy>=m) continue;

            int w=(g[gx][gy]!=op[i]);//通过两点间是否需要旋转计算权值


            //假设i，j,dist[q[i].x][q[i].y]==dist[q[j].x][q[j].y],i点可以通过i+1更新t点，j则通过j+0更新t点，队列中i在j的前面，则会先更新i连接的t点
            //此时dist(t)改变，进入队列且位于x+1那段，然后更新到了j点，发现dist(t)变小，需要再次将t点入队，加入x那段
            //此时t这个点入队两次，x和x+1两端都有，但是只有前面那段会被出队用来更新其他点，出队后就被标记，作用消失
            //所以每次对可以连接的点一定要判断已经的dist(t)和通过i点或j点可以更新dist(i)+0||1的大小，并通过权值判断加入头还是尾
            if(dist[nx][ny]>dist[tx][ty]+w)
            {
                dist[nx][ny]=dist[tx][ty]+w;

                if(w==0) q.push_front({nx,ny});//权值为0插入对头

                else q.push_back({nx,ny});//权值为1插入队尾
            }
        }
    }
    return -1;
}
int main()
{
    int k;
    cin>>k;
    while(k--)
    {
        cin>>n>>m;
        for(int i=0;i<n;i++)
        scanf("%s",g[i]);
        if(n+m &1) puts("NO SOLUTION");//这里是取巧，n+m必须为偶数才能到达，要不然bfs()会返回-1，这里则直接判断不需要bfs();
        else printf("%d\n",bfs());
    }
}

算法2()// 未完待续

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla