UVA 1600 Patrol Robot 巡逻机器人（BFS）

女爷i 2024-02-17 19:04 61阅读 0赞

需要注意的一点是：障碍物可以访问多次（因为当访问此障碍物时，当前路径穿过的连续障碍物次数大于或小于以前的路径也可以访问该点（也许以前的路径并不能走到终点））

#include<cstdio>
    #include<cstring>
    #include<queue>
    using namespace std;
    const int maxn=20+2;
    struct node{
    	int x,y,obs;        //obs 表示当前连续穿过的障碍物 
    	node(int x=0,int y=0,int obs=0):x(x),y(y),obs(obs){}
    };
    int p[maxn][maxn];
    int d[maxn][maxn][maxn];
    int n,m,k;
    int dir[][2]={
       {-1,0},{1,0},{0,1},{0,-1}};
    bool isValid(node &nd){
    	return nd.x>=1 && nd.x<=n && nd.y>=1 && nd.y<=m; 
    }
    void bfs(){
    	memset(d,0,sizeof(d));
    	queue<node> q;
    	q.push(node(1,1,0));
    	while(!q.empty()){
    		node u=q.front();
    		q.pop();
    		if(u.x==n && u.y==m){
    			printf("%d\n",d[u.x][u.y][0]);
    			return ;
    		}
    		for(int i=0;i<4;i++){
    			node v=node(u.x+dir[i][0],u.y+dir[i][1],0);
    			if(isValid(v)){
    				if(!p[v.y][v.x] && !d[v.x][v.y][0]){ //如果不是障碍物，并且没有访问过 
    					q.push(v);
    					d[v.x][v.y][0]=d[u.x][u.y][u.obs]+1; //obs表示穿过的障碍物，如果为0,那么此点一定不是障碍物1 
    				}
    				else if(p[v.y][v.x]==1 && u.obs<k && !d[v.x][v.y][u.obs+1]){ //如果是障碍物 
    				v.obs=u.obs+1;
    				q.push(v);
    				d[v.x][v.y][v.obs]=d[u.x][u.y][u.obs]+1;
    				} 
    			}
    		}
    	}
    	printf("-1\n");
    }
    int main(){
    	int T;
    //	freopen("in.txt","r",stdin);
    	scanf("%d",&T);
    	while(T--){
    		scanf("%d%d",&m,&n);
    		scanf("%d",&k);
    		for(int i=1;i<=m;i++)
    		 for(int j=1;j<=n;j++)
    		   scanf("%d",&p[i][j]);
    		   bfs();
    	} 
    	return 0;
    }

如有不当之处，欢迎指出，谢谢!