巡逻机器人（BFS）

巡逻机器人问题（F - BFS,推荐）

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 (1 $\le$ m, n $\le$ 20). The second line contains an integer number k(0 $\le$ k $\le$ 20). 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
 
题目大意： 
机器人要从一个M*N（１ｍ, ｎ２０）网格的左上角（1,1）走到右下角（M,N）。网格中的一些格子是空地（用0表示），其他格子是障碍（用1表示）。
机器人每次可以往4个方向走一格，但不能连续的穿越k(0k20)个障碍，求最短路长度。起点和终点保证是空地。

分析：
求最短路径,即最优解问题，采用BFS。
1.可以跨过一个障碍，但不能连续跨障碍。
2.边界点没有4个方向
3.要将走过的点进行标记


代码：

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

View Code

心得：

BFS的题自己还是不会写，要看别人AC的代码才会。还是要多看一些别人的优秀代码来仿写，加油吧，争取自己能写好的代码。