题目描述

blablabla

参考文献

在这个题目中，我们很容易发现，我们走的路只能是对角线，所以坐标变化为 $(1,1),(1,-1),(-1,1),(-1,-1)$，同时我们发现如果一个对角线没有连接上，我们只用一步旋转就能进行转换。所以图中的线路显然也会对我们进行影响。

不妨将图中的每个交点看作一个结点，并且编号。同时再给每一个方格进行编号

接下来可以根据每次选择移动方向，定位到对应的格子。

剩下最后一个关键点，就是如何判断两个结点之间我们需要的是什么路径，这个可以调节对应坐标变化，使得前两两个和后两个分别为对应的电线。

C++ 代码

#include<bits/stdc++.h>
#define re register
using namespace std;

const int INF=0x3f3f3f3f;
const int N=600;
struct Node
{
    int x,y;
};

int dira[4][2]={{1,1},{-1,-1},{-1,1},{1,-1}};
int dirb[4][2]={{1,1},{0,0},{0,1},{1,0}};
char s[N][N];
int d[N][N];
int t,n,m;

inline bool valid(int x,int y)
{
    return x>=0 && x<=n && y>=0 && y<=m;
}

inline void bfs()
{
    deque<Node> q;
    memset(d,0x3f,sizeof(d));
    d[0][0]=0;
    q.push_front((Node){0,0});
    while(!q.empty())
    {
        Node now=q.front();q.pop_front();
        for(re int k=0;k<4;++k)
        {
            int x=now.x+dira[k][0],y=now.y+dira[k][1];
            int xx=now.x+dirb[k][0],yy=now.y+dirb[k][1];
            if(valid(x,y)==0)continue;
            char ned=k<2?'\\':'/';
            int t=1;
            if(ned==s[xx][yy])t=0;
            if(d[x][y]>d[now.x][now.y]+t)
            {
                d[x][y]=d[now.x][now.y]+t;
                if(t==0)
                    q.push_front((Node){x,y});
                else q.push_back((Node){x,y});
            }
        }

    }
}

int main()
{
//  freopen("a.in","r",stdin);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(re int i=1;i<=n;++i)
            scanf("%s",s[i]+1);
        bfs();
        if(d[n][m]<INF)
            cout<<d[n][m]<<endl;
        else cout<<"NO SOLUTION"<<endl;
    }

    return 0;
}