#include <bits/stdc++.h>
using namespace std;
constexpr int N = 507;
constexpr int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
string cs = R"(\/\/)";
constexpr int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
struct node {
int x, y;
};
char g[N][N];
int n, m;
int dist[N][N];
bool st[N][N];
int bfs() {
memset(dist, 0x3f, sizeof(dist));
dist[0][0] = 0;
deque<node> dq;
dq.push_back({0, 0});
while (!dq.empty()) {
node t = dq.front();
dq.pop_front();
if (st[t.x][t.y]) continue;
st[t.x][t.y] = true;
for (int i = 0; i < 4; i++) {
int xx = t.x + dx[i], yy = t.y + dy[i];
if (xx < 0 || xx > n || yy < 0 || yy > m) continue;
int ca = t.x + ix[i], cb = t.y + iy[i];
int d = dist[t.x][t.y] + (g[ca][cb] != cs[i]);
if (d < dist[xx][yy]) {
dist[xx][yy] = d;
if (g[ca][cb] != cs[i]) {
dq.push_back({xx, yy});
} else {
dq.push_front({xx, yy});
}
}
}
}
return dist[n][m];
}
int main() {
int op;
cin>>op;
while(op--) {
cin >> n >> m;
for (int i = 0; i < n; i++) cin >> g[i];
int t = bfs();
if (t == 0x3f3f3f3f) {
cout << "NO SOLUTION\n";
} else {
cout << t << "\n";
}
}
return 0;
}
请各位大佬帮忙看看