欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P1126 机器人搬重物

程序员文章站 2022-06-12 09:38:25
...

题目描述

机器人移动学会(RMI)现在正尝试用机器人搬运物品。机器人的形状是一个直径$1.6米的球。在试验阶段,机器人被用于在一个储藏室中搬运货物。储藏室是一个N×MN×M的网格,有些格子为不可移动的障碍。机器人的中心总是在格点上,当然,机器人必须在最短的时间内把物品搬运到指定的地方。机器人接受的指令有:向前移动11步(Creep);向前移动2步(Walk);向前移动33步(Run);向左转(Left);向右转(Right)。每个指令所需要的时间为11秒。请你计算一下机器人完成任务所需的最少时间。

输入输出格式

输入格式:

 

第一行为两个正整数N,M(N,M≤50)N,M(N,M≤50),下面NN行是储藏室的构造,00表示无障碍,11表示有障碍,数字之间用一个空格隔开。接着一行有44个整数和11个大写字母,分别为起始点和目标点左上角网格的行与列,起始时的面对方向(东EE,南SS,西WW,北NN),数与数,数与字母之间均用一个空格隔开。终点的面向方向是任意的。

 

输出格式:

 

一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出−1−1。

P1126 机器人搬重物

 

输入输出样例

输入样例#1: 复制

9 10
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0 1 0
0 0 0 1 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0 0 0
0 0 0 0 0 1 0 0 0 0
0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
1 0 0 0 0 0 0 0 1 0
7 2 2 7 S

输出样例#1: 复制

12

总结回顾:

下次一定不能花这么多时间做这种题了。

1.广搜的优势在于一步到位,不重复更新一个点,越早搜到就越短,适合权值相等的时候,但是每条路径权值不等的时候要对搜过的点进行更新,一定要开辅助权值函数

2.这个题的移动物体占用四个格,判断障碍物时需要判断两个格,但是判断是否搜索过只需要判断标记格。

 

#include <bits/stdc++.h>
using namespace std;

struct point{
    int pos[2];
    char dir;             //记录入点的方向
    int cost;
    bool operator ==(const point b){
        return this->pos[0]==b.pos[0]&&this->pos[1]==b.pos[1];
    }
}start,endp;
bool f[100][100]={false};
int mat[100][100],cb=0,cost[100][100];    
queue<point>que;
stack<point>sta;
void push_in(point p,point t){
    
    int px=p.pos[0],py=p.pos[1],tx=t.pos[0],ty=t.pos[1];
    if(p.dir==t.dir)cost[px][py]=cost[tx][ty]+1;
    else cost[px][py]=cost[tx][ty]+2;
    f[px][py]=true;
    que.push(p);
//    printf("t:(%d,%d) and p:(%d,%d) t.dir:%c and p.dir:%c",t.pos[0],t.pos[1],p.pos[0],p.pos[1],t.dir,p.dir);
//    printf("   p.cost:%d\n",cost[px][py]);
}

void sta_push(point t){
    while (!sta.empty()) {
        push_in(sta.top(),t);
        sta.pop();
    }
}

void bfs(point s){
    que.push(s);
    f[s.pos[0]][s.pos[1]]=true;
    bool succ=false;
    while (!que.empty()) {
        point t = que.front();
        int x=t.pos[0],y=t.pos[1],i=1;
        que.pop();
        if(t==endp){
            printf("%d",cost[x][y]);
            succ=true;
            break;
        }
        for(i=1;i<4;i++){        //为了搜索更快,一个点三种移动情况由快到慢依次入队
            if(mat[x-i][y]==0&&mat[x-i][y+1]==0);
            else break;
            if(!f[x-i][y]||cost[x][y]+1<cost[x-i][y])sta.push({{x-i,y},'N',0});
        }sta_push(t);
        
        for(i=1;i<4;i++){
            if(mat[x+i+1][y]==0&&mat[x+i+1][y+1]==0);
            else break;
            if(!f[x+i][y]||cost[x][y]+1<cost[x+i][y])sta.push({{x+i,y},'S',0});
        }sta_push(t);
        
        for(i=1;i<4;i++){
            if(mat[x][y-i]==0&&mat[x+1][y-i]==0);
            else break;
            if(!f[x][y-i]||cost[x][y]+1<cost[x][y-i])sta.push({{x,y-i},'W',0});
        }sta_push(t);
        
        for(int i=1;i<4;i++){
            if(mat[x][y+1+i]==0&&mat[x+1][y+1+i]==0);
            else break;
            if(!f[x][y+i]||cost[x][y]+1<cost[x][y+i])sta.push({{x,y+i},'E',0});
        }sta_push(t);
    }
    if(!succ)cout<<"-1"<<endl;
}

int main() {
 memset(mat, -1, sizeof(int)*100*100);
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%d",&mat[i][j]);
    scanf("%d %d %d %d %c",&start.pos[0],&start.pos[1],&endp.pos[0],&endp.pos[1],&start.dir);
    if(mat[endp.pos[0]][endp.pos[1]]!=0)cout<<"-1";
    else bfs(start);
    return 0;
}