题解 UVA1600 【巡逻机器人 Patrol Robot】
Chouquet
·
·
题解
在“不能连续穿越 $k$ 个障碍”的条件下，机器人每到一个位置，如果它先前也到过这个位置但是两次连续穿越的障碍数不一样，那么机器人也是可以走到这个位置的。所以用 $vis[x][y][k]$ 表示机器人是否到过 $(x,y)$ 这个位置且连续穿越的障碍数为 $k$ ，目的 **只是为了使结果更优** 。
其他的就是普通的搜索了吧QWQ，代码：
```cpp
#include <cstdio>
#include <cstring>
#include <queue>
struct Node {
int x, y, s, step;
};//s为连续穿过的障碍个数
int t, m, n, k, a[23][23];
const int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
bool vis[25][25][531];//注意第三维的大小
int main() {
scanf("%d", &t);
while (t--) {
scanf("%d%d%d", &m, &n, &k);
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &a[i][j]);
std::queue<Node> q;
memset(vis, 0, sizeof vis);
q.push((Node){1, 1, 0, 0});
bool ok = 0;//ok判断能否找到解
while (!q.empty()) {
Node t = q.front();
q.pop();
if (t.x == m && t.y == n) {//找到解，输出
printf("%d\n", t.step);
ok = 1;
break;//注意是多组数据，不能直接return 0;
}
vis[t.x][t.y][t.s] = 1;
for (int i = 0; i < 4; i++) {
int tx = t.x + dx[i], ty = t.y + dy[i];
if (tx >= 1 && tx <= m && ty >= 1 && ty <= n) {
if (a[tx][ty] && t.s + 1 <= k && !vis[tx][ty][t.s + 1])//这里判断的是走到(tx,ty)的情况
q.push((Node){tx, ty, t.s + 1, t.step + 1});
else if (!a[tx][ty] && !vis[tx][ty][0])
q.push((Node){tx, ty, 0, t.step + 1});//如果这个位置为空地，连续穿过的空地数显然为0
}
}
}
if (!ok)
puts("-1");
}
return 0;
}
```