https://www.luogu.com.cn/problem/P4667

求调QAQ

#include <bits/stdc++.h>
#define maxn 1000005
using namespace std;
inline int read(){
    int x = 0 , f = 1 ; char c = getchar() ;
    while( c < '0' || c > '9' ) { if( c == '-' ) f = -1 ; c = getchar() ; } 
    while( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } 
    return x * f ;
}
struct edge{
    int v, w, nxt;
}e[maxn];
int head[maxn], cnt;
void add(int u, int v, int w){
    e[++cnt] = {v, w, head[u]}, head[u] = cnt;
} 
int n, m;
char a1 = '\\', a2 = '/';
int vis[maxn], dis[maxn];
void bfs(){
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    deque<int> q;
    q.push_front(1), vis[1] = 1, dis[1] = 0;
    while(!q.empty()){
        int x = q.front(); q.pop_front();
        for(int i = head[x]; i; i = e[i].nxt){
            int y = e[i].v;
            if(vis[y]) continue;
            vis[y] = 1;
            int z = e[i].w;
            if(z == 0) q.push_front(y);
            else q.push_back(y);
            if(dis[y] > dis[x] + z) dis[y] = dis[x] + z;
        }
    }
}
int main() {
    n = read(), m = read();
    if((m + n) % 2){
        cout << "NO SOLUTION";
        return 0;
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            char c;
            cin >> c;
            if(c == a1){
                add((i - 1) * (m + 1) + j, i * (m + 1) + j + 1, 0);
                add(i * (m + 1) + j, (i - 1) * (m + 1) + j + 1, 1);
                add(i * (m + 1) + j + 1, (i - 1) * (m + 1) + j, 0);
                add((i - 1) * (m + 1) + j + 1, i * (m + 1) + j, 1);
            }
            if(c == a2){
                add((i - 1) * (m + 1) + j, i * (m + 1) + j + 1, 1);
                add(i * (m + 1) + j, (i - 1) * (m + 1) + j + 1, 0);
                add(i * (m + 1) + j + 1, (i - 1) * (m + 1) + j, 1);
                add((i - 1) * (m + 1) + j + 1, i * (m + 1) + j, 0);
            }
        }
    }
    bfs();
    if(vis[(n + 1) * (m + 1)]) cout << dis[(n + 1) * (m + 1)];
    else cout << "NO SOLUTION";
}