Acwing175——电路维修

    每个方格的四个角看成是节点 如果节点与节点之间有斜线链接
就把两个节点间的权值设为0 否则设为1 (看成是需要转一次) 这样
就得到一张边权为1或0的无向图 使用bfs+deque 在每个节点上沿
分支扩展时 如果时权值为0的边从队头入队 如果是权值为1的边从
队尾入队


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

typedef pair< int, int > PII;
const int N = 510;
char g[N][N];
int n, m;
int dist[N][N];
int dx[4] = {-1, 1, 1, -1};
int dy[4] = {-1, -1, 1, 1}; //dx dy 是节点往左上 右上 左下 右下 的坐标偏移量
int ix[4] = {-1, 0, 0, -1}; //ix iy 是节点的左上 上 左 节点本身坐标 代表方格中电线的摆放位置
int iy[4] = {-1, -1, 0, 0};
char str[] = "\\/\\/";
bool st[N][N];

int bfs()
{
    memset( dist, 0x3f, sizeof dist );
    dist[0][0] = 0;

    deque< PII > q;
    q.push_front( {0, 0} );

    while( q.size() )
    {
        PII t = q.front();
        q.pop_front();

        int x = t.first, y = t.second;

        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];
            int j = x + ix[i], k = y + iy[i];

            if( a >= 0 && a <= n && b >= 0 && b <= m )
            {
                int w = 0;
                if( g[j][k] != str[i] )
                    w = 1;

                if( dist[a][b] > dist[x][y] + w )
                {
                    dist[a][b] = dist[x][y] + w;

                    if( w )
                        q.push_back( {a, b} );
                    else
                        q.push_front( {a, b} );
                }
            }
        }
    }
    if( dist[n][m] == 0x3f3f3f3f )
        return -1;
    else
        return dist[n][m];

}

int main()
{
    int T;
    cin >> T;
    while( T -- )
    {
        memset( st, 0, sizeof st );

        cin >> n >> m;

        for( int i = 0; i < n; i ++ )
            cin >> g[i];

        int t = bfs();

        if( t == -1 )
            cout << "NO SOLUTION" << endl;
        else
            cout << t << endl;
    }
}