|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 510;
|
|
|
|
|
|
const int INF = 0x3f3f3f3f;
|
|
|
|
|
|
typedef pair<int, int> PII;
|
|
|
|
|
|
|
|
|
|
|
|
// 2178 ms
|
|
|
|
|
|
int n, m;
|
|
|
|
|
|
char g[N][N];
|
|
|
|
|
|
bool st[N][N];
|
|
|
|
|
|
int dist[N][N];
|
|
|
|
|
|
|
|
|
|
|
|
//点偏移：左上 左下 右下 右上
|
|
|
|
|
|
int dx[] = {-1, 1, 1, -1};
|
|
|
|
|
|
int dy[] = {-1, -1, 1, 1};
|
|
|
|
|
|
//格子偏移：(1,1)->(0,0),(1,1)->(1,0),(1,1)->(1,1),(1,1)->(0,1)
|
|
|
|
|
|
int ix[] = {-1, 0, 0, -1};
|
|
|
|
|
|
int iy[] = {-1, -1, 0, 0};
|
|
|
|
|
|
//标准姿势
|
|
|
|
|
|
char cs[] = "\\/\\/";
|
|
|
|
|
|
|
|
|
|
|
|
int getNum(int x, int y) {
|
|
|
|
|
|
/*
|
|
|
|
|
|
* 按点看 ，为 0,1,2,3,4,...,m
|
|
|
|
|
|
* 按格子看，为 1,2,3,4,...,m
|
|
|
|
|
|
即按点看，每行m+1个点
|
|
|
|
|
|
推广公式化： 编号 = 行号(可以从0开始，也可以从1开始)*列的数量 + 列号
|
|
|
|
|
|
*/
|
|
|
|
|
|
return x * (m + 1) + y; //按点看，共m+1列
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
void bfs() {
|
|
|
|
|
|
//多组测试数据，重新初始化
|
|
|
|
|
|
memset(st, 0, sizeof st);
|
|
|
|
|
|
|
|
|
|
|
|
//距离初始化，注意全部初始化为正无穷，并且，需要指定出发点距离为0
|
|
|
|
|
|
memset(dist, 0x3f, sizeof dist);
|
|
|
|
|
|
dist[0][0] = 0;
|
|
|
|
|
|
|
|
|
|
|
|
//小顶堆
|
|
|
|
|
|
priority_queue<PII, vector<PII>, greater<PII>> q;
|
|
|
|
|
|
//将距离0，点号为0入小顶堆
|
|
|
|
|
|
q.push({0, getNum(0, 0)});
|
|
|
|
|
|
|
|
|
|
|
|
while (q.size()) {
|
|
|
|
|
|
PII u = q.top();
|
|
|
|
|
|
q.pop();
|
|
|
|
|
|
|
|
|
|
|
|
//距离
|
|
|
|
|
|
int distance = u.first;
|
|
|
|
|
|
|
|
|
|
|
|
//点号 还原回 坐标
|
|
|
|
|
|
int x = u.second / (m + 1), y = u.second % (m + 1);
|
|
|
|
|
|
|
|
|
|
|
|
//第一次出队列的是最小值，后出的没用
|
|
|
|
|
|
if (st[x][y]) continue;
|
|
|
|
|
|
//标记为已出队过
|
|
|
|
|
|
st[x][y] = true;
|
|
|
|
|
|
|
|
|
|
|
|
for (int i = 0; i < 4; i++) {
|
|
|
|
|
|
//到哪个点
|
|
|
|
|
|
int tx = x + dx[i], ty = y + dy[i];
|
|
|
|
|
|
//出界
|
|
|
|
|
|
if (tx < 0 || tx > n || ty < 0 || ty > m) continue;
|
|
|
|
|
|
//走哪个格子
|
|
|
|
|
|
int cx = x + ix[i], cy = y + iy[i];
|
|
|
|
|
|
|
|
|
|
|
|
int d;
|
|
|
|
|
|
if (g[cx][cy] == cs[i]) //如果要走的格式与零成本的一致，则不收钱
|
|
|
|
|
|
d = dist[x][y];
|
|
|
|
|
|
else
|
|
|
|
|
|
d = dist[x][y] + 1; //否则收1元钱
|
|
|
|
|
|
|
|
|
|
|
|
if (d < dist[tx][ty]) { //是不是可以更新最小距离
|
|
|
|
|
|
dist[tx][ty] = d;
|
|
|
|
|
|
q.push({d, getNum(tx, ty)}); //入小顶堆
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
//加快读入
|
|
|
|
|
|
cin.tie(0), ios::sync_with_stdio(false);
|
|
|
|
|
|
int T;
|
|
|
|
|
|
cin >> T;
|
|
|
|
|
|
while (T--) {
|
|
|
|
|
|
// n行m列
|
|
|
|
|
|
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)
|
|
|
|
|
|
printf("NO SOLUTION\n");
|
|
|
|
|
|
else
|
|
|
|
|
|
printf("%d\n", dist[n][m]);
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
