UVa 1600 Patrol Robot(BFS)

题意：

　　给定一个n*m的图，有一个机器人需要从左上角（1，1）到右下角（n，m），网格中一些格子是空地，一些格子是障碍，机器人每次能走4个方向，但不能连续穿越k（0<= k <= 20）个障碍物，求最短路径，如无法到达输出 -1。

分析：

　对于空地，建一个vis数组记录走过的空地，然后每次碰到没vis过的空地都把队伍K更新为最大值， vis这块地。

　　对于墙的情况，我们可以建一个vis1数组去记录通过墙时候的k值，如果之前有一个k值比现在要通过的大，那么我们就不入队，否则入队，入队k是队头k-1，更新这堵墙的k值。

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 int G[maxn][maxn];

 int vis[maxn][maxn];

 int visk[maxn][maxn];

 int dx[] = {,,,-};//右下左上

 int dy[] = {,,-,};

 struct node{

     int x,y, step, k;

     node(int x, int y, int step, int k):x(x), y(y), step(step), k(k){}

 };

 int n, m, k;

 bool vaild(int x, int y){

     if(x <  || x >= n || y <  || y >= m)

         return false;

     return true;

 }

 int main(){

     int T;

     scanf("%d", &T);

     while(T--){

         memset(G,,sizeof(G));

         memset(vis,,sizeof(vis));

         memset(visk,,sizeof(visk));

         scanf("%d %d", &n, &m);

         scanf("%d", &k);

         for(int i = ; i < n; i++){

             for(int j = ; j < m; j++){

                 scanf("%d", &G[i][j]);

             }

         }

     int ok = ;

     queue<node> q;

     q.push(node(,,,k));

     visk[][] = k;

     vis[][] = ;

         int cnt = ;

         while(!q.empty()){

             node t = q.front(); q.pop();

 //            printf("%d %d %d %d\n", t.x,t.y, t.step, t.k);

             if(t.x == n- && t.y == m-){

                 printf("%d\n",t. step );

                 ok = ;

                 break;

             }

             for(int i = ; i < ; i++){

                 int tx = t.x + dx[i];

                 int ty = t.y + dy[i];

                 if(vaild(tx,ty)){

                     if(G[tx][ty] == ){

                         if( t.k -  >=  && visk[tx][ty] <= t.k - ){

 //                            if(!vis[tx][ty]){

                                 q.push(node(tx,ty,t.step+, t.k - ));

                                 visk[tx][ty] = t.k - ;

 //                                vis[tx][ty] = 1;

 //                            }

                         }

                     }

                     else {

                         if(!vis[tx][ty]){

                             q.push(node(tx,ty,t.step+,k));

                             vis[tx][ty] = ;

                         }

                     }

                 }

             }

         }

         if(!ok) printf("-1\n");

     }

     return ;

 }

巴特西

UVa 1600 Patrol Robot(BFS)

题意：

分析：

最新文章

热门文章