题目描述
达达是来自异世界的魔女,她在漫无目的地四处漂流的时候,遇到了善良的少女翰翰,从而被收留在地球上。
翰翰的家里有一辆飞行车。
有一天飞行车的电路板突然出现了故障,导致无法启动。
电路板的整体结构是一个R行C列的网格(R,C≤500),如下图所示。
样例
输入样例:
1
3 5
\\/\\
\\///
/\\\\
输出样例:
1
算法1
(宽搜) $O(n)$
代码里的ix
表示字符数组在g[N][N];
的下标。
时间复杂度
参考文献
C++ 代码
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
using namespace std;
typedef pair<int, int> PII;
const int N = 510;
int n, m;
char g[N][N];
int d[N][N];
bool st[N][N];
int bfs(){
memset(st, 0, sizeof st);
memset(d, 0x3f, sizeof d);
deque<PII> q;
q.push_back({0, 0});
d[0][0] = 0;
int dx[4] = {-1, -1, 1, 1}, dy[4] = {-1, 1, 1, -1};
int ix[4] = {-1, -1, 0, 0}, iy[4] = {-1, 0, 0, -1};
char cs[] = "\\/\\/";
while (q.size()){
auto t = q.front(); q.pop_front();
int x = t.first, y = t.second;
if (st[x][y]) continue;
st[x][y] = true;//标记true表示第一次出队,即为起点到当前点的最小值
for (int i = 0; i < 4; i ++){
int a = x + dx[i], b = y + dy[i];
int j = x + ix[i], k = y + iy[i];
if (a >= 0 && a <= n && b >= 0 && b <= m){//因为需要考虑到(0, 1) 或者(1, 0)这些点所以一定要a >= 0 && b >= 0 不能写成 a > 0 && b > 0
int w = 0;
if (g[j][k] != cs[i]) w = 1;
if (d[a][b] > d[x][y] + w){
d[a][b] = d[x][y] + w;
if (w) q.push_back({a, b});
else q.push_front({a, b});
}
}
}
}
if (d[n][m] == 0x3f3f3f3f) return -1;
return d[n][m];
}
int main(){
int T;
scanf("%d", &T);
while (T --){
scanf("%d%d", &n, &m);
for (int i = 0; i < n; i ++) scanf("%s", g[i]);
int t = bfs();
if (t == -1) puts("NO SOLUTION");
else printf("%d\n", t);
}
return 0;
}