Uva 1600 Patrol Robot
题目：洛谷·UVa439 题意 输入一个m*n矩阵表示地图，其中1表示障碍，0表示空地。机器人要从m*n地图的(1,1)走到(m,n)，每次可以往上下左右的其中一个方向走一格，且最多只能连续跨过k个障碍。数据满足1 <= m, n <= 20， 0 <= k <= 20 分析 首先我们可以确认这不是普通的BFS求最短路（对比：Uva 439），但题目多了一个条件——最多能连续跨过k个障碍，这意味着只用二位数组不足以判断题目条件 于是我试着用访问数组int vis[maxn][maxn][2]存储访问状态，其中vis[x][y][0]表示从该格再走一步后的步数，vis[x][y][1]表示走到该格需要跨越的障碍数。但这种思路存在问题：程序无法区分跨越不同数量的障碍走到同一格，而是把它们视为同一条路线 只需稍加改进，用bool vis[maxn][maxn][maxn]存储访问状态即可，其中vis[x][y][cnt]表示连续跨越cnt个障碍后到达(x,y) 利用结构体存储坐标、步数和连续跨越障碍的数量，方便BFS的入队出队操作（因为只需一个队列） 代码 C++ #include <iostream> #include <queue> #include <cstring> using namespace std; const int maxn = 25; int pic[maxn][maxn]; // 读入地图 bool vis[maxn][maxn][maxn]; // 访问数组，判断是否曾连续跨过若干个障碍到达某格 const int dx[4] = {0, 1, 0, -1}; // 偏移量 const int dy[4] = {1, 0, -1, 0}; int t, m, n, k; struct Node { int x; int y; int step; // 当前步数 int cnt; // 当前连续跨越障碍的数量 }; void read_lines() { cin >> m >> n >> k; for (int i = 1; i <= m; i++) for (int j = 1; j <= n; j++) cin >> pic[i][j]; } bool check(int x, int y) { // 检查是否出界 if (x < 1 || y < 1 || x > m || y > n) return true; return false; } int bfs(int x, int y, int k) { Node t = {x, y, 0, 0}; queue<Node> q; q.push(t); while (!q.empty()) { t = q.front(); if (t.x == m && t.y == n) return t.step; for (int i = 0; i < 4; i++) { int px = t.x + dx[i], py = t.y + dy[i]; if (check(px, py)) continue; // 出界 Node tmp = {px, py, t.step, t.cnt}; // 一定要用临时变量来操作！ if (pic[px][py]) tmp.cnt++; // 该格为障碍 else tmp.cnt = 0; // 该格为空地 if (tmp.cnt <= k && !vis[px][py][tmp.cnt]) { // 连续跨越障碍数量<=k且未曾连续跨过t.cnt个障碍到达(px,py) tmp.step++; vis[px][py][tmp.cnt] = true; // 已访问 q.push(tmp); } } q.pop(); } return -1; } int main() { #ifdef LOCAL freopen("patrol_robot.in", "r", stdin); freopen("patrol_robot.out", "w", stdout); #endif ios::sync_with_stdio(false); //取消cin与stdin的同步，加速输入输出 cin.tie(0); // 解除cin与cout的绑定，进一步加快执行效率 cout.tie(0); cin >> t; while (t--) { memset(vis, false, sizeof(vis)); // 记得清零！ read_lines(); cout << bfs(1, 1, k) << "\n"; } return 0; } 我们知道cin和cout输入输出的速度比不上printf和scanf，因此可以通过一些小技巧来加速： ...
