首页 > 代码库 > 洛谷 1126 机器人搬重物
洛谷 1126 机器人搬重物
1126 机器人搬重物
题目描述
机器人移动学会（RMI）现在正尝试用机器人搬运物品。机器人的形状是一个直径1.6米的球。在试验阶段，机器人被用于在一个储藏室中搬运货物。储藏室是一个N*M的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，当然，机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有：向前移动1步（Creep）；向前移动2步（Walk）；向前移动3步（Run）；向左转（Left）；向右转（Right）。每个指令所需要的时间为1秒。请你计算一下机器人完成任务所需的最少时间。
输入输出格式
输入格式：
输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
输出格式：
一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出-1。
输入输出样例
输入样例#1：
9 100 0 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 1 00 0 0 1 0 0 0 0 0 00 0 1 0 0 0 0 0 0 00 0 0 0 0 0 1 0 0 00 0 0 0 0 1 0 0 0 00 0 0 1 1 0 0 0 0 00 0 0 0 0 0 0 0 0 01 0 0 0 0 0 0 0 1 07 2 2 7 S
#include<cstdio>#include<queue>#include<cstring>#include<iostream>using namespace std;int a[51][51],n,m;bool v[51][51][5];int dx[4]={-1,0,1,0};int dy[4]={0,1,0,-1};int sx,sy;struct node{ int x,y,step; int to;}cur,nxt;queue<node>q;void bfs(){ q.push(cur); v[cur.x][cur.y][cur.to]=1; while(!q.empty()) { cur=q.front(); q.pop(); int xx,yy; int k=cur.to; int x=cur.x,y=cur.y; for(int i=1;i<=3;i++) { xx=cur.x+i*dx[k]; yy=cur.y+i*dy[k]; if(xx>0&&xx<n&&yy>0&&yy<m&&!a[xx][yy]&&!a[xx+1][yy]&&!a[xx][yy+1]&&!a[xx+1][yy+1]) { if(xx==sx&&yy==sy) { printf("%d",cur.step+1); return; } if(v[xx][yy][k]) continue; v[xx][yy][k]=true; nxt.x=xx; nxt.y=yy; nxt.step=cur.step+1; nxt.to=k; // printf("(%d %d)-->(%d %d) %d %d\n",cur.x,cur.y,nxt.x,nxt.y,nxt.to,nxt.step); q.push(nxt); } else break; } nxt.x=cur.x; nxt.y=cur.y;nxt.step=cur.step+1; nxt.to=(cur.to+1)%4; if(!v[nxt.x][nxt.y][nxt.to]) { v[nxt.x][nxt.y][nxt.to]=true; q.push(nxt); //printf("(%d %d)-->(%d %d) %d %d\n",cur.x,cur.y,nxt.x,nxt.y,nxt.to,nxt.step); } nxt.to=(cur.to-1+4)%4; if(!v[nxt.x][nxt.y][nxt.to]) { v[nxt.x][nxt.y][nxt.to]=true; q.push(nxt); //printf("(%d %d)-->(%d %d) %d %d\n",cur.x,cur.y,nxt.x,nxt.y,nxt.to,nxt.step); } } printf("-1");}int main(){ //freopen("1","w",stdout); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&a[i][j]); scanf("%d%d",&cur.x,&cur.y); cur.step=0; scanf("%d%d",&sx,&sy); char c; cin>>c; switch(c) { case ‘N‘: cur.to=0;break; case ‘E‘: cur.to=1;break; case ‘S‘: cur.to=2;break; case ‘W‘: cur.to=3;break; } if(cur.x==sx&&cur.y==sy) { printf("0\n"); return 0; } bfs();}
if(v[xx][yy][k]) continue;
这一句不能加到上面的if一起判断
因为
洛谷 1126 机器人搬重物
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。