UVA 1600 Patrol Robot(BFS扩展)

Time Limit: 3000MS

Memory Limit: Unknown

64bit IO Format: %lld & %llu

Description

A robot has to patrol around a rectangular area which is in a form of mxn 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 (1m, n20). The second line contains an integer number k(0k20). The i^th line of the next m lines contains n integer a_ij separated by space (i = 1, 2,..., m;j= 1, 2,..., n). The value of a_ij 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 Output

7 
10 
-1

题目大意：

　　这道题是说，给你一个n*m的0-1矩阵，你要做的就是在这个矩阵中，从(1,1)走到(n,m)所需要的最小步数，但是你有一个功能，就是可以连续穿过k个1。

解题思路：

　　看到最少操作次数，想都不用想，直接上bfs，然后node的设计就是x，y，k，step，这个k要注意下。

　　当我们扩展到下一层的时候a[tx][ty]==1的时候，newnode.kk = now.k-1;当a[tx][ty] == 0 的时候，newnode.kk = k;

　　相当于这个机器人在下一步走到1的时候就减少一点血，当走到0的时候，就满血满蓝了。

　　一开始在newnode.kk = now.kk - 1;和 now.kk-=1;的设计上挂掉了第二组样例，原因很简单，就是说，如果我把提前把newnode搞出来，而是一味

　　的靠now.kk去更新的话，会产生错误的结果.

代码：

  1 # include<cstdio>
  2 # include<iostream>
  3 # include<queue>
  4 # include<cstring>
  5 
  6 using namespace std;
  7 
  8 # define MAX 23
  9 
 10 int a[MAX][MAX];
 11 int nxt[4][2] = {{1,0},{0,-1},{-1,0},{0,1}};
 12 int book[MAX][MAX][MAX];
 13 
 14 int n,m,k;
 15 
 16 struct node
 17 {
 18     int x,y;
 19     int step;
 20     int kk;
 21 };
 22 queue<node>Q;
 23 
 24 void init()
 25 {
 26     while (!Q.empty())
 27     {
 28         Q.pop();
 29     }
 30     memset(book,0,sizeof(book));
 31 }
 32 
 33 int can_move( int x ,int y,int kk )
 34 {
 35     if ( x>=1&&x<=n&&y>=1&&y<=m&&book[x][y][kk]==0 )
 36         return 1;
 37     else
 38         return 0;
 39 }
 40 
 41 int bfs ( node start )
 42 {
 43     init();
 44     if ( start.x==n&&start.y==m )
 45     {
 46         return start.step;
 47     }
 48 
 49     Q.push(start);
 50     while ( !Q.empty() )
 51     {
 52         node now = Q.front();
 53         Q.pop();
 54         if ( now.kk < 0 )
 55             continue;
 56         for ( int i = 0;i < 4;i++ )
 57         {
 58             node newnode;
 59             int tx = now.x+nxt[i][0], ty = now.y+nxt[i][1];
 60             if ( a[tx][ty]==1 )
 61                 newnode.kk = now.kk-1;
 62             else
 63                 newnode.kk = k;
 64             if ( can_move(tx,ty,newnode.kk) )
 65             {
 66                 if ( tx==n&&ty==m )
 67                 {
 68                     return now.step+1;
 69                 }
 70                 newnode.x = tx; newnode.y = ty; newnode.step = now.step+1;
 71             if( newnode.kk >= 0 )
 72             {
 73                 Q.push(newnode);
 74                 book[tx][ty][newnode.kk] = 1;
 75             }
 76             }
 77         }
 78     }
 79 
 80     return -1;
 81 
 82 
 83 }
 84 
 85 
 86 
 87 int main(void)
 88 {
 89     int t;scanf("%d",&t);
 90     while ( t-- )
 91     {
 92         scanf("%d%d%d",&n,&m,&k);
 93         for ( int i = 1;i <= n;i++ )
 94         {
 95             for ( int j = 1;j <= m;j++ )
 96             {
 97                 scanf("%d",&a[i][j]);
 98             }
 99         }
100         node start;
101         start.x = 1; start.y = 1;start.step = 0; start.kk = k;
102         book[start.x][start.y][start.kk] = 1;
103         int ans = bfs(start);
104         if ( ans == -1 )
105             printf("-1
");
106         else
107             printf("%d
",ans);
108 
109     }
110 
111     return 0;
112 }