1170: 暴躁机器人

时间限制: 1 Sec  内存限制: 128 MB
提交: 17  解决: 7
[提交] [状态] [讨论版] [命题人:test]

题目描述

PIPI发明了一个暴躁机器人，机器人位于一个 n*m 的网格中, 网格中的一些格子是空地(数字0表示)，另一些是障碍物(数字1表示)，暴躁机器人从左上角(1,1)出发前往右下角(n,m), 机器人每一步可以往上下左右四个方向走一个，由于机器人很暴躁，所以它可以摧毁障碍物。但是它最多连续穿过k 个障碍物，求机器人从左上角到右下角的最短路长度。 保证起点和终点是空地。

输入

输入包含一个正整数T，代表测试用例个数。 
对于每组测试用例，第一行包含三个整数 n,m,k (1<=n,m<=20, 0<=k <=20)。 
接下来包含一个 n*m 的01矩阵，代表网格矩阵。 

输出

对于每组测试用例，输出机器人从左上角走到右下角的最少步数。若无法到达右下角，输出 -1 。

样例输入

1
3 6 1
0 1 1 0 0 0
0 0 1 0 1 1
0 1 1 1 1 0

样例输出

9

提示

测试用例的走法: (1,1) -> (2,1) -> (2,2) -> (2,3) ->(2,4) -> (1,4) -> (1,5) -> (1,6) -> (2,6) -> (3,6) . 路径长度为 9. 

来源/分类

中等搜索

今天被这道题拦住了。

原因倒是不难理解，如果像传统搜索题那样只用二维数组记录一个坐标是否已被访问，由于访问路径的先后顺序问题，可能错过最优解或者错判为无解。所以关键在于怎样容纳多次访问重复的坐标，而且还要做必要的剪枝。

因为初始不熟悉这类问题，看答案都看不明白，不懂为什么只要用三维数组控制障碍数，不需要管其他指标，而且最后结果不需要去比较所有层级的最小值。

等到最后想明白究竟搜索时在控制什么指标，其他人的答案也就看明白了。

其实有两个重要指标：机器人走到某个坐标时，1. 走的步数，2. 当前剩余的突破能力。每个坐标都维护这些阈值，如果机器人走过来，走的步数小于当前坐标记录的最小值，或者突破能力大（如果此处是障碍），都可以入队列继续搜索，否则就抛弃，因为之前已经有更优的解了。

要理解别人的答案，注意几个点。由于BFS的特性，可以保证第一次走到此坐标时一定是最短距离。三维数组的第三维就是在记录到此为止突破的障碍数，每一层只访问一次，不重复，但不同的层级可以多次访问同一坐标，层级之间并没有顺序关系。剩余的突破能力应该越大越好，不过这一点可以忽略不去控制，多几次入队没有本质影响。因为突破能力弱的要么到不了终点，要么是之前拆墙走了捷径所以最终到达终点时用的步数可能要少一些。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <queue>
#include <unordered_set>

using namespace std;

const int MAX = 1 << 30;

struct point {
  int x;  // location
  int y;
  int able;  // ability left to go through obstacle
  int steps;
  point(int x=0, int y=0, int able=0, int steps=0): x(x), y(y), able(able), steps(steps) {}
};

bool valid(int x, int y, vector<vector<int>> &arr) {
  return x >= 0 && x < arr.size() && y >= 0 && y < arr[0].size();
}


int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  #ifndef ONLINE_JUDGE
  freopen("3.in", "r", stdin);
  freopen("3.out", "w", stdout);
  #endif
  int T;
  int n, m, k;
  cin >> T;
  for (int cs=1; cs <= T; cs++) {
    cin >> n >> m >> k;
    vector<vector<int>> arr(n, vector<int>(m));
    vector<vector<point>> v(n, vector<point>(m, point(0, 0, 0, MAX)));
    for(int i=0; i<n; i++) {
      for(int j=0; j<m; j++) {
        cin >> arr[i][j];
      }
    }
    queue<point> q;
    point p = point(0, 0, k, 0);
    q.push(p);
    v[0][0].steps = 0;
    v[0][0].able = k;

    int able;
    vector<int> m1 = {1, -1, 0, 0};
    vector<int> m2 = {0, 0, 1, -1};
    int x, y;
    while(!q.empty()) {
      p = q.front();
      q.pop();
      x = p.x;
      y = p.y;
      
      if(x == n-1 && y == m-1) {
        break;
      }
      for(int i=0; i<4; i++) {
        int nx = m1[i] + x;
        int ny = m2[i] + y;
        if(valid(nx, ny, arr) ) {
          bool flag = false;
          if(arr[nx][ny] == 0) {
            if(v[nx][ny].steps > p.steps + 1) {
              v[nx][ny].steps = p.steps + 1;
              q.push(point(nx, ny, k, p.steps+1));
            }
          }
          else if (p.able > 0) {
            if(v[nx][ny].steps > p.steps + 1) {
              v[nx][ny].steps = p.steps + 1;
            }
            else if(p.able > v[nx][ny].able) {
              v[nx][ny].able = p.able;
            }
            else {
              continue;
            }
            q.push(point(nx, ny, p.able-1, p.steps+1));
          }
        }
      }
    }

    if(v[n-1][m-1].steps != MAX) {
      cout << v[n-1][m-1].steps << "\n";
    }
    else {
      cout << "-1\n";
    }
  }
  return 0;
}