一、题意

有一个巡逻机器人要从一个n*m的网格的左上角走到右上角，网格中0为空地，1为障碍物。
该机器人具备连续通过k个障碍物的能力，求最短路径长度。

二、解析

最短路径考虑bfs。同样需要确定bfs的“状态点”如何定义。
考虑到该机器人穿障碍物的能力（在障碍物中也可以拐弯），因此需要把它该能力的剩余“能量点”（初始为k）作为状态之一。注意作为状态后vis将要变成3维。

三、代码

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int maxn = 20 + 5, maxm = 20 + 5, maxk = 20 + 5;
const int Fx[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node {
    int x, y, dist, remain;
    node(int x, int y, int dist, int remain) : x(x), y(y), dist(dist), remain(remain) {}
};
int kase, n, m, k;
int a[maxn][maxm], vis[maxn][maxm][maxk];

void bfs(int x0, int y0) {
    queue<node> que;
    que.push(node(x0, y0, 0, k)), vis[x0][y0][k] = 1;
    int ans = -1;
    while(!que.empty()) {
        node u = que.front();
        que.pop();
        // cout << "u=(" << u.x << "," << u.y << ")" << endl;
        if(u.x == n - 1 && u.y == m - 1) {
            ans = u.dist;
            break;
        }
        for(int i = 0; i < 4; i ++) {
            int nx = u.x + Fx[i][0], ny = u.y + Fx[i][1];
            // cout << "v=(" << nx << "," << ny << ")" << endl;
            if(nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if(a[nx][ny] == 1) {
                if(vis[nx][ny][u.remain - 1] || u.remain - 1 < 0) continue;
                que.push(node(nx, ny, u.dist + 1, u.remain - 1));
                vis[nx][ny][u.remain - 1] = 1;
            }
            else {
                if(vis[nx][ny][k]) continue;
                que.push(node(nx, ny, u.dist + 1, k));
                vis[nx][ny][k] = 1;
            }
        }
    }
    cout << ans << endl;
}

int main() {
    cin >> kase;
    while(kase --) {
        cin >> n >> m >> k;
        for(int i = 0; i < n; i ++) for(int j = 0; j < m; j ++) cin >> a[i][j];
        memset(vis, 0, sizeof(vis));
        bfs(0, 0);
    }
}

四、归纳

  • 只要抓准了bfs的状态点是什么，bfs的题目基本就能迎刃而解了