题意理解

对照书上的中文理解起来最快。

3
2 5
0
0 1 0 0 0
0 0 0 1 0
4 6
1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0
0 1 1 1 0 0
2 2
0
0 1
1 0

理解一下上面的样例输入：

3 表示数据集一共用三个。

下面的三组数据集中，以第一个数据集举例。

• 第一行，2 和 5 分别是 m 行和 n 列。
• 第二行，0 表示有 0 个涡轮加速器，也就是说，一个障碍物都过不了。
• 之后几行就是实际的每一个点的情况了。

代码理解

// Patrol Robot, ACM/ICPC Hanoi 2006, UVa1600
// 陈锋
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <functional>
#include <queue>
using namespace std;

#define _for(i, a, b) for (int i = (a); i < (b); ++i)
bool inRange(int x, int l, int r) {
  return (l > r) ? inRange(x, r, l) : (l <= x && x <= r);
}

struct Point {
  int x, y;
  Point(int x = 0, int y = 0) : x(x), y(y) {}
};
typedef Point Vector;
Vector operator+(const Vector &A, const Vector &B) {
  return Vector(A.x + B.x, A.y + B.y);
}
bool operator==(const Point &a, const Point &b) {
  return a.x == b.x && a.y == b.y;
}

const int MAXN = 24;
int M, N, K, Grid[MAXN][MAXN], vis[MAXN][MAXN][MAXN];
bool isValid(const Point &p) {
  return inRange(p.x, 0, M - 1) && inRange(p.y, 0, N - 1);
}
Vector dirVs[4] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

struct Stat {
  Point pos;
  int turbo;
};

int &getVisd(const Stat &s) { return vis[s.pos.x][s.pos.y][s.turbo]; }

int solve() {
  Stat s;
  Point dest(M - 1, N - 1);
  s.pos.x = 0;
  s.pos.y = 0;
  s.turbo = 0;
  memset(vis, -1, sizeof(vis));

  queue<Stat> q;
  q.push(s);
  vis[s.pos.x][s.pos.y][s.turbo] = 0;

  while (!q.empty()) {
    const Stat &f = q.front();
    q.pop();
    const int &fd = getVisd(f);
    if (f.pos == dest)
      return fd;
    assert(f.turbo <= K);

    _for(i, 0, 4) {
      Point np = f.pos + dirVs[i];
      if (!isValid(np))
        continue;
      int isBlock = Grid[np.x][np.y];
      if (isBlock && f.turbo + 1 > K)
        continue;

      Stat ns = {np, (isBlock ? (f.turbo + 1) : 0)};
      int &d = getVisd(ns);
      if (d == -1) {
        d = fd + 1;
        q.push(ns);
      }
    }
  }

  return -1;
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &M, &N, &K);
    _for(i, 0, M) _for(j, 0, N) scanf("%d", &(Grid[i][j]));
    int ans = solve();
    printf("%d\\n", ans);
  }
}

// 1627141	LA3670	Patrol Robot	Accepted	C++	0.003
// 2015-01-15 03:05:38

需要处理几个疑问：

1、为什么 vis 是三维数组？

遍历到当前的某一个点的时候，第三维是用的涡轮加速器的数量。一个涡轮加速器可以过一个障碍，两个就可以过两个连续的障碍物。这个三维数组，比如 vis[s.pos.x][s.pos.y][s.turbo] 中，存放的是当前这个点并且使用了 s.turbo 个涡轮加速器之后的当前最优值。

2、getVisd(const Stat &s) 函数如何理解？

这个函数名取得不好。这里的 d 可能是 distance 的意思。表示 s 状态下的最优路径的距离。为什么这个值就是最优的呢？因为这里使用的是队列，并且，这个队列模拟的是 bfs，所谓 bsf，就是一圈一圈往外扩散，所以，如果当前所在的这一圈有一个是终点了，那么，最优值自然就出来了。