美妙的acm

H__恶魔猎手会飞了

Time Limit:3000MS  Memory Limit:65536K
Total Submit:60 Accepted:15

Description

恶魔猎手成功拿到了古尔丹之颅，吸收了古尔丹之颅的力量后，恶魔猎手全身变的一片漆黑，后背上也长出了一对翅膀，也就是说：他会飞了！！
兴奋一阵子后，他发现了他的困境，他出不去了！！
因为在路上他消耗了太多的生命值，吸收古尔丹之颅又花费了他很大力气，他发现他现在非常虚弱，不能再承受任何伤害了。但他又欣喜的发现，吸收了古尔丹之颅的力量后他的身体变的异常强化，一般的小怪不能再对他造成任何伤害了，而且他能飞了，在空中他不会受到任何伤害，但是他发现他的翅膀非常奇怪，每次一定要飞行k距离才能停下来，两点间(x1,y1)(x2,y2)的距离定义为|x1-x2|+|y1-y2|。为了更好的熟悉他的新翅膀，他决定完全靠飞出去而不去步行。
问恶魔猎手在不受到任何伤害的情况下最少需要飞行几次，才能到达出口（1，1），他现在处于（n，n）位置。

Input

输入有多组数据。
每组由n+1行构成。
第一行两个数n(1<=n<=500)，k(1<=k<=n)；
第二行到第n+1行，是一个n行n列的01矩阵，0代表在该点恶魔猎手不会受到伤害，1代表会受到伤害。

Output

输出恶魔猎手在不受到任何伤害的情况下最少需要飞行几次，才能到达出口。如果不能到达出口，输出-1；

Sample Input

5 2
0 1 0 1 0
1 0 1 0 1
0 1 1 1 0
1 0 1 0 1
1 1 0 1 0
5 2
1 0 1 1 1
1 1 0 1 1
1 0 1 0 0
1 0 0 0 0
0 0 0 0 0

Sample Output

4
-1

  1 // 1713H__恶魔猎手会飞了用bfs广搜解决最优的问题
  2
  3 #include < iostream >
  4 #include < queue >
  5 #include < memory >
  6 using   namespace  std;
  7
  8 int  map[ 501 ][ 501 ]; // 地图
  9 int  flag[ 501 ][ 501 ]; // 标记点的遍历
 10 int  n,k;
 11 int  divx[ 4 ] = { 1 , 1 , - 1 , - 1 } ; // x四个方向
 12 int  divy[ 4 ] = { 1 , - 1 , 1 , - 1 } ; // y的四个方向
 13
 14 struct  data // 保存广度遍历的三个信息
 15 {
 16      int  x,y;
 17      int  step;
 18 } head,N;
 19
 20 queue < data > que; // 定义一个队列
 21
 22 void  bfs() // 从(n,n)开始广搜遍历
 23 {
 24      int  i,j;
 25     
 26     head.x = n;head.y = n;head.step = 0 ; // 起始点
 27     
 28     flag[n][n] = 1 ; // 标记
 29     
 30     que.push(head); // 将第一个结点压入
 31     
 32      int  p = 0 ; // 是否找到的标志
 33     
 34      while ( ! que.empty()) // 是一个关键的地方,也是一个终止的地方
 35      {
 36         data temp;
 37         
 38         temp = que.front();que.pop(); // 先得到头结点，然后压出头结点，利用队列的关键
 39         
 40          if ( temp.x == 1 && temp.y == 1  ) // 结尾
 41          {
 42             p = 1 ; // 找到
 43             cout << temp.step << endl;
 44              break ;
 45         }
 46         
 47          // 以k的距离在周围广搜
 48          for (i = 0 ;i <= k;i ++ ) // (x的大小取值)例如k=2,x可以+0,1,2,
 49          {
 50              for (j = 0 ;j < 4 ;j ++ ) // 四个方向的取值
 51              {
 52                  int  tx = temp.x + i * divx[j]; // 大小乘以方向
 53                  int  ty = temp.y + (k - i) * divy[j];
 54                  int  tstep = temp.step + 1 ; //
 55                 
 56                  // 判断tx,ty是否满足条件：没有超出范围,没有遍历过,这一点没有危险
 57                  // 满足条件才能压入
 58                  if (tx >= 1 && tx <= n && ty >= 1 && ty <= n && flag[tx][ty] == 0 && map[tx][ty] == 0 )
 59                  {
 60                     flag[tx][ty] = 1 ;
 61                     data tp; // 暂时实用的结构体
 62                     tp.x = tx;
 63                     tp.y = ty;
 64                     tp.step = temp.step + 1 ;
 65                     que.push(tp); // 压入的操作    
 66                 }
 67             }
 68         }
 69     }
 70     
 71      if (p == 0 ) // 没有找到
 72         cout << " -1 " << endl;
 73      while ( ! que.empty())     // 清空队列,初始化
 74         que.pop();
 75     
 76 }
 77
 78 int  main()
 79 {
 80      int  i,j;
 81      while (cin >> n >> k)
 82      {
 83         memset(map, 0 , sizeof (map)); // 初始化
 84         memset(flag, 0 , sizeof (flag)); //
 85         
 86     
 87          for (i = 1 ;i <= n;i ++ ) // 建立一个地图
 88              for (j = 1 ;j <= n;j ++ )
 89                 cin >> map[i][j];
 90             
 91              if (map[ 1 ][ 1 ] == 1 ) // 如果一开始的时候(1,1)入口已经关掉
 92              {
 93                 cout << " -1 " << endl;
 94                  continue ;
 95             }
 96             
 97             bfs();    
 98     }
 99      return   0 ;
100 }