题意：
机器人走迷宫求最小步数，不同之处在于机器人最多能一次连续穿过k堵墙。
要点：
BFS模板题稍微有些变换，将vis数组增加到三维来记录穿墙数即可，因为有的时候就算坐标相同，但穿过墙数不同也是不同的。
#include#include #include #include using namespace std;int map[50][50],vis[50][50][50];//visit多一维来记录穿墙数int m, n, k;int d[4][2] = { {1,0},{-1,0},{0,1},{0,-1} };struct node{ int x, y; int count; int layer;//用layer记录穿墙数};int bfs(int x,int y){ memset(vis, 0, sizeof(vis)); queue q; node c; c.x = x; c.y = y; c.count = 0;c.layer=0; q.push(c); vis[x][y][0] = 1; while (!q.empty()) { node c = q.front(); q.pop(); if (c.x == m&&c.y == n) return c.count; for (int i = 0; i < 4; i++) { node v; v.x = c.x + d[i][0]; v.y = c.y + d[i][1]; v.layer = c.layer; if (map[v.x][v.y]) v.layer++; //遇到墙则穿墙数+1 else v.layer = 0; //如果不穿墙，穿墙数归零 v.count = c.count + 1; if (v.layer<=k&&!vis[v.x][v.y][v.layer]&&v.x>=1&&v.x<=m&&v.y>=1&&v.y<=n) { vis[v.x][v.y][v.layer] = 1;//这里多一维的目的是有时候坐标相同但穿墙数不同也是能经过的 q.push(v); } } } return -1;}int main(){ int t; scanf("%d", &t); while (t--) { int i,j; scanf("%d%d", &m, &n); scanf("%d", &k); for (i = 1; i <= m; i++) for (j = 1; j <= n; j++) scanf("%d", &map[i][j]); printf("%d\n", bfs(1,1)); } return 0;}