UVA 1600 Patrol Robot bfs

63 阅读 0 评论 42 点赞

我是靠谱客的博主重要爆米花，最近开发中收集的这篇文章主要介绍UVA 1600 Patrol Robot bfs，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给出一个网格，这个网格中有一些障碍，求从左上角右下角的最短距离，且不能连续穿过K个障碍。

分析：求最短路径嘛，首先想到的肯定会是bfs，那怎么判断连续K个障碍呢？因为是连续的嘛，所以如果下一个要搜的点不是障碍，那么它的k就是0了，然后因为要考虑障碍点了，所以不能简单地只记录已经扫过的点了，还要排除k值得影响，所以我这里加了一个K的数组来表示当前点的k值大小，如果要搜的点的k值比记录的小那么即使已经扫过也可以继续放入队列中。但我这里写的太恶心了。。。自己都有点嫌弃了。。如果有耐心的话可以自己再将细节优化一下。。毕竟有点长。。。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
const int maxed=22;
struct Node
{
    int x,y,cur,k;
};
int k,r,c,p[maxed][maxed],min_,sum[maxed][maxed];//这里的sum数组就是用来记录k值得，不断更新它的值就好了
bool vis[maxed][maxed];
int main()
{
    //freopen("123.txt","w",stdout);
    void slove();
    int N;
    scanf("%d",&N);
    while(N--){
        min_=-1;
        scanf("%d%d%d",&r,&c,&k);
        memset(vis,false,sizeof(vis));
        memset(sum,INF,sizeof(sum));
        for(int i=1;i<=r;i++)
            for(int j=1;j<=c;j++)
                scanf("%d",&p[i][j]);
        vis[1][1]=true;
        slove();
//        cout<<"sdasda"<<endl;
//        for(int i=1;i<=r;i++){
//            for(int j=1;j<=c;j++)
//                cout<<vis[i][j]<<" ";
//            cout<<endl;
//        }
//        cout<<"sdadsadsadsa"<<endl;
        printf("%dn",min_);
    }
    return 0;
}
void slove()
{
    Node n;
    n.x=1,n.y=1,n.cur=0,n.k=0;
    queue<Node> qu;
    qu.push(n);
    while(!(qu.empty())){
        Node no;
        n=qu.front();qu.pop();
        //cout<<n.x<<" "<<n.y<<" "<<n.cur<<" "<<n.k<<endl;
        if(n.k>k)
            continue;
        if(n.x==r&&n.y==c){
            min_=n.cur;
            break;
        }
        no.cur=n.cur+1;                      //接下来就是让他向上下左右走，这里其实可以用两个dx，dy数组来进行方位的转换。。可以节省很多代码。。但。。。当时比较恶心。。就直接这么写的了。
        if(n.x+1<=r&&n.y<=c&&n.y>=1){
                no.x=n.x+1;no.y=n.y;
                if(p[n.x+1][n.y])
                    no.k=n.k+1;
                else
                    no.k=0;
                if(!vis[n.x+1][n.y]||no.k<sum[n.x+1][n.y]){
                    vis[n.x+1][n.y]=true;
                    qu.push(no);
                    sum[n.x+1][n.y]=min(sum[n.x+1][n.y],no.k);
                }
        }
        if(n.x-1>=1&&n.y<=c&&n.y>=1){
                no.x=n.x-1;no.y=n.y;
                if(p[n.x-1][n.y])
                    no.k=n.k+1;
                else
                    no.k=0;
                if(!vis[n.x-1][n.y]||no.k<sum[n.x-1][n.y]){
                    vis[n.x-1][n.y]=true;
                    qu.push(no);
                    sum[n.x-1][n.y]=min(sum[n.x-1][n.y],no.k);
                }
        }
        if(n.y+1<=c&&n.x>=1&&n.x<=r){
                //cout<<"qqqqqqqqqqqqqqqqqqqqq"<<endl;
                no.x=n.x;no.y=n.y+1;
                if(p[n.x][n.y+1])
                    no.k=n.k+1;
                else
                    no.k=0;
                if(!vis[n.x][n.y+1]||no.k<sum[n.x][n.y+1]){
                    vis[n.x][n.y+1]=true;
                    qu.push(no);
                    sum[n.x][n.y+1]=min(sum[n.x][n.y+1],no.k);
                }
        }
        if(n.y-1>=1&&n.x>=1&&n.x<=r){
            no.x=n.x;no.y=n.y-1;
            if(p[n.x][n.y-1])
                no.k=n.k+1;
            else
                no.k=0;
            if(!vis[n.x][n.y-1]||no.k<sum[n.x][n.y-1]){
                vis[n.x][n.y-1]=true;
                qu.push(no);
                sum[n.x][n.y-1]=min(sum[n.x][n.y-1],no.k);
            }
        }
    }
}