电路维修

题目描述：

n*m的网格，每个网格上都有一根电线，电线有初始状态，连接左上到右下，或者连接右上到左下，你可以改变若干根电线的状态，使的左上角的格子的左上角能到达右下角的格子的右下角，问最少改变次数

思路：

可以看成改变状态为1，不改变状态为0，这样就可以用01bfs来求最短路

难在到底该怎么跑bfs

这里的方法是，n*m的格子上有(n+1)*(m+1)个点，我们bfs的是红色的这(n+1)*(m+1)个点，一个点(2, 2)能跑到四个红色的点，需要开一个dx和dy数组来记录，现在还需要知道是否需要扭转电线，也就是看黑色的四个点的坐标对应的电线的状态，可以发现，他们和中间的那个红色的起点也是有坐标可以对应过去的，所以我们就再开一个idx和idy数组来记录，跑bfs的时候遇到不需要改变状态的点，就把他塞到队头，否则塞到队尾，为了防止走重复的点，开一个vis数组标记一下

其中坐标(x, y)，当x + y是奇数的时候是永远到不了的，因为每次走都是沿对角线，x + y的和总是进行偶数数量的变化，所以不会走到奇数的位置去

//Work by: Chelsea
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define sd(n) scanf("%d",&n)
#define sdd(n,m) scanf("%d %d",&n,&m)
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define debug(a) cout << "Debuging...|" << #a << ": " << a << "\n";
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m;
char tr[505][505];

int dx[] = {-1, -1, 1, 1};
int dy[] = {-1, 1, -1, 1};
int ix[] = {-1, -1, 0, 0};
int iy[] = {-1, 0, -1, 0};
char p[] = {"\\//\\"};
int dis[505][505];
bool vis[505][505];
bool judge(int x, int y){
    if(x > n + 1 || x < 1 || y > m + 1 || y < 1)return false;
    return true;
}

void bfs(){
    deque<pii>q;
    mem(dis, inf);dis[1][1] = 0;
    q.push_back(m_p(1, 1));
    while (!q.empty()) {
        auto [x, y] = q.front();q.pop_front();
        if(vis[x][y])continue;
        vis[x][y] = 1;
        if(x == n + 1 && y == m + 1){
            cout << dis[x][y] << endl;
            return;
        }
        for(int i = 0; i < 4; ++i){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(judge(xx, yy)){
                int idx = x + ix[i];
                int idy = y + iy[i];
                if(tr[idx][idy] == p[i]){
                    q.push_front(m_p(xx, yy));
                    dis[xx][yy] = min(dis[xx][yy], dis[x][y]);
                }
                else{
                    q.push_back(m_p(xx, yy));
                    dis[xx][yy] = min(dis[xx][yy], dis[x][y] + 1);
                }
            }
        }
    }
}


void work(){
    cin >> n >> m;
    mem(vis, 0);
    for(int i = 1; i <= n; ++i){
        for(int j = 1; j <= m; ++j){
            cin >> tr[i][j];
        }
    }
    if((n + m) % 2)cout << "NO SOLUTION\n";
    else bfs();
}


int main(){
    io;
    int tt;cin>>tt;
    for(int _t = 1; _t <= tt; ++_t){
        work();
    }
    return 0;
}