|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
|
typedef pair<int, int> PII;
|
|
|
#define x first
|
|
|
#define y second
|
|
|
|
|
|
const int N = 510;
|
|
|
int n, m; // n行m列
|
|
|
char g[N][N]; // 地图
|
|
|
|
|
|
int dist[N][N]; // 距离出发点的距离
|
|
|
bool st[N][N]; // 是不是走过(重复入队)
|
|
|
|
|
|
// 左上，右上，右下，左下
|
|
|
// 如果与cs[i]的字符相匹配，表示现在就是你想要的路线，不需要花钱，否则交1元钱
|
|
|
char cs[] = "\\/\\/";
|
|
|
// 点的四个偏移量
|
|
|
int dx[] = {-1, -1, 1, 1};
|
|
|
int dy[] = {-1, 1, 1, -1};
|
|
|
// 踩格子的偏移量
|
|
|
int ix[] = {-1, -1, 0, 0};
|
|
|
int iy[] = {-1, 0, 0, -1};
|
|
|
|
|
|
deque<PII> q; // 双端队列主要解决图中边的权值只有0或者1的最短路问题
|
|
|
void bfs() {
|
|
|
// 多组数据，清空
|
|
|
q.clear();
|
|
|
memset(dist, 0x3f, sizeof dist);
|
|
|
memset(st, 0, sizeof st);
|
|
|
|
|
|
// 将{0,0}入队列，第一个要搜索的位置
|
|
|
dist[0][0] = 0;
|
|
|
q.push_back({0, 0});
|
|
|
|
|
|
while (q.size()) {
|
|
|
PII t = q.front();
|
|
|
q.pop_front();
|
|
|
|
|
|
if (st[t.x][t.y]) continue; // 走过的不再走
|
|
|
st[t.x][t.y] = true; // 标识已走过
|
|
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
|
int x = t.x + dx[i], y = t.y + dy[i];
|
|
|
if (x < 0 || x > n || y < 0 || y > m) continue; // 出界
|
|
|
|
|
|
// 走向这个点需要经过哪个格子
|
|
|
int a = t.x + ix[i], b = t.y + iy[i];
|
|
|
|
|
|
// 通过是否匹配计算权值是0，还是1，修改距离
|
|
|
int d = dist[t.x][t.y] + (g[a][b] != cs[i]);
|
|
|
|
|
|
// 发现更小值
|
|
|
if (d < dist[x][y]) {
|
|
|
dist[x][y] = d; // 更新更小值
|
|
|
// 权值为1，加队尾
|
|
|
// 权值为0，加队头
|
|
|
g[a][b] == cs[i] ? q.push_front({x, y}) : q.push_back({x, y});
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
}
|
|
|
|
|
|
int main() {
|
|
|
int T;
|
|
|
cin >> T;
|
|
|
while (T--) {
|
|
|
cin >> n >> m;
|
|
|
|
|
|
for (int i = 0; i < n; i++)
|
|
|
for (int j = 0; j < m; j++)
|
|
|
cin >> g[i][j];
|
|
|
|
|
|
// 双端队列宽搜
|
|
|
bfs();
|
|
|
|
|
|
// 如果无法取得最短路
|
|
|
if (dist[n][m] == INF)
|
|
|
puts("NO SOLUTION");
|
|
|
else
|
|
|
printf("%d\n", dist[n][m]);
|
|
|
}
|
|
|
return 0;
|
|
|
} |
