Dijkstra每次向格点的四个方向连

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

const int maxn = 5e6 + 5;
inline int read() {
    int x = 0 , f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') {
            f = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
inline void write(int x) {
    char F[200];
    int tmp = x > 0 ? x : -x;
    if (x < 0) {
        putchar('-');
    }
    int cnt = 0;
    while (tmp > 0) {
        F[cnt ++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (cnt > 0) {
        putchar(F[-- cnt]);
    }
}
typedef struct {
    int y , z , next;
} Edge;
Edge edge[maxn];
struct Node {
    int k;
    long long dis;
    Node (int k_ , long long dis_) {
        k = k_;
        dis = dis_;
    }
};
bool operator < (Node a , Node b) {
    return a.dis > b.dis;
}
int n , m;
char str;
int E = 0;
int elast[maxn];
inline void add_edge(int x , int y , int z) {
    E ++;
    edge[E].y = y;
    edge[E].z = z;
    edge[E].next = elast[x];
    elast[x] = E;
}
int a , b;
int vis[maxn];
long long dis[maxn] ;
inline void Dijkstra() {
    a = 1;
    b = (n + 1) * (m + 1);
    for (int i = 0 ; i <= (n + 1) * (m + 1) ; i ++) {
        dis[i] = LONG_LONG_MAX;
        vis[i] = 0;
    }
    dis[a] = 0;
    priority_queue<Node> q;
    q.push(Node(a , 0));
    while (!q.empty()) {
        int k = q.top().k;
        q.pop();
        if (vis[k]) continue;
        if (k == b) break;
        vis[k] = 1;
        for (int j = elast[k] ; j ; j = edge[j].next) {
            int v = edge[j].y;
            if (dis[v] > dis[k] + edge[j].z) {
                dis[v] = dis[k] + edge[j].z;
                q.push(Node(v , dis[v]));
            }
        }
    }
}
int T;
bool flag = false;
int main() {
    cin >> T;
    while (T --) {
        scanf("%d%d" , &n , &m);
        flag = false;
        if ((n + m) & 1) {
            flag = true;
        }
        for (int i = 1 ; i <= E ; i ++) {
            elast[i] = 0;
        }
        E = 0;
        for (int i = 1 ; i <= n ; i ++) {
            for (int j = 1 ; j <= m ; j ++) {
                cin >> str;
                if (flag == false) {
                    if (str == '/') {
                        add_edge((i) * (m + 1) + j , (i - 1) * (m + 1) + j + 1, 0);
                        add_edge((i - 1) * (m + 1) + j + 1, (i) * (m + 1) + j , 0);
                        add_edge((i) * (m + 1) + j + 1, (i - 1) * (m + 1) + j , 1);
                        add_edge((i - 1) * (m + 1) + j , (i) * (m + 1) + j + 1, 1);
                    } else {
                        add_edge((i) * (m + 1) + j , (i - 1) * (m + 1) + j + 1, 1);
                        add_edge((i - 1) * (m + 1) + j + 1, (i) * (m + 1) + j , 1);
                        add_edge((i) * (m + 1) + j + 1, (i - 1) * (m + 1) + j , 0);
                        add_edge((i - 1) * (m + 1) + j , (i) * (m + 1) + j + 1, 0);
                    }
                }

            }
        }
        if (flag == true) {
            printf("NO SOLUTION\n");
            continue;
        } 

        Dijkstra();
        printf("%lld\n" , dis[(n + 1) * (m + 1)]);
    }



}