UVA1600-Patrol Robot（BFS进阶）

Problem UVA1600-Patrol Robot

Accept：529  Submit：4330

Time Limit: 3000 mSec

Problem Description

A robot has to patrol around a rectangular area which is in a form of m × n grid (m rows and n columns). The rows are labeled from 1 to m. The columns are labeled from 1 to n. A cell (i,j) denotes the cell in row i and column j in the grid. At each step, the robot can only move from one cell to an adjacent cell, i.e. from (x,y) to (x + 1,y), (x,y + 1), (x−1,y) or (x,y −1). Some of the cells in the grid contain obstacles. In order to move to a cell containing obstacle, the robot has to switch to turbo mode. Therefore, the robot cannot move continuously to more than k cells containing obstacles. Your task is to write a program to find the shortest path (with the minimum number of cells) from cell (1, 1) to cell (m,n). It is assumed that both these cells do not contain obstacles.

 Input

The input consists of several data sets. The first line of the input file contains the number of data sets which is a positive integer and is not bigger than 20. The following lines describe the data sets. For each data set, the first line contains two positive integer numbers m and n separated by space (1 ≤ m,n ≤ 20). The second line contains an integer number k (0 ≤ k ≤ 20). The i-th line of the next m lines contains n integer aij separated by space (i = 1,2,...,m; j = 1,2,...,n). The value of aij is ‘1’ if there is an obstacle on the cell (i,j), and is ‘0’ otherwise.

 Output

For each data set, if there exists a way for the robot to reach the cell (m,n), write in one line the integer number s, which is the number of moves the robot has to make; ‘-1’ otherwise.

 Sample Input

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
 

 

 Sample Ouput

7

10

-1

题解：自己做的第一道可以穿过障碍物的搜索，原来做的都相当于k==0的情况，这个题里多了一个可以穿越障碍物，但不能连续穿越多个的限制，这时再用一般的套路是会出错的。做过八数码的同学应该有感觉，BFS搜索中，判重是一件至关重要的事情，它可以避免大量无谓的搜索以及神奇的死循环。这里如果把判重数组定义成二维vis，就只能判断是否到过这里，而忽略了还能穿越几个障碍物这一参数。很有可能从两条路过来，长度相同但是其中一条还可以穿越更多的障碍，还有可能虽然暂时性的其中一条路到这里的时间戳较早，但是它能够继续穿越的障碍物也较少，对最终结果来说不如一条时间戳稍晚，但是还能穿越很多障碍物的路线，这些情况会被二维vis提前堵死，是很不可取的。解决方案就是vis数组加一维表示穿越了几个障碍物到达这里，这样再去判重就没问题了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <queue>
using namespace std;

struct Point{
    int x,y,time;
    int layer;
    Point(int x = 0,int y = 0,int time = 0,int layer = 0) :
        x(x),y(y),time(time),layer(layer) {}
};

const int maxn = 22;
int gra[maxn][maxn];
int vis[maxn][maxn][maxn];
int n,m,k;
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,-1,1};

int bfs(){
    queue<Point> que;
    que.push(Point(1,1,0,0));
    memset(vis,0,sizeof(vis));
    vis[1][1][0] = 1;
    while(!que.empty()){
        Point first = que.front();que.pop();
        if(first.x==n && first.y==m) return first.time;
        int xx,yy;
        for(int i = 0;i < 4;i++){
            xx = first.x+dx[i],yy = first.y+dy[i];
            if(1<=xx && 1<=yy && xx<=n && yy<=m){
                int layer = first.layer;
                if(gra[xx][yy]) layer++;
                else layer = 0;
                if(layer<=k && !vis[xx][yy][layer]){
                    vis[xx][yy][layer] = 1;
                    que.push(Point(xx,yy,first.time+1,layer));
                }
            }
        }
    }
    return -1;
}

int main()
{
    //freopen("input.txt","r",stdin);
    int iCase;
    scanf("%d",&iCase);
    while(iCase--){
        scanf("%d%d",&n,&m);
        scanf("%d",&k);
        for(int i = 1;i <= n;i++){
            for(int j = 1;j <= m;j++){
                scanf("%d",&gra[i][j]);
            }
        }
        printf("%d
",bfs());
    }
    return 0;
}