Luogu P1126 机器人搬重物 题解

发表于 | 分类于

Luogu P1126 机器人搬重物 题解

题目描述

机器人移动学会（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： 

1
2
3
4
5
6
7
8
9
10
11
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： 

1
12

本题思路不难，无非就是广搜的一步变成123步或者转向而已，麻烦的是对地图的理解……本人写的时候卡了2小时在地图的处理，然后才A掉。

还有坑点，就是起点可能和终点重合，需要特判。

对地图的理解：

一开始我采用了化格子为点的做法，先弄个可行点地图再搞，然而WA了，只好换。

后来我用的就是AC的做法，在图上制造虚空点，每个点四周的4个格子都得是0才能通过，只要有一个是1就过不了。

附代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
struct node
{
    int x,y,face;
    friend bool operator ==(const node a,const node b)
    {
        if(a.x!=b.x) return false;
        if(a.y!=b.y) return false;
        if(a.face!=b.face) return false;
        return true;
    }
}st,di,fx[4];
queue<node>q;
char dire;
int n,m,ans[60][60]={0};
bool d[60][60]={false},v[60][60][4]={false};
void spfa()
{
    int &sum=ans[di.x][di.y];
    q.push(st);
    v[st.x][st.y][st.face]=true;
    while(!q.empty())
    {
        node t=q.front();
        q.pop();
        v[t.x][t.y][t.face]=false;
        for(int i=0;i<4;i++)
        {
            int ti;
            node tmp=t;
            tmp.face=i;
            if(tmp.face+t.face==3) ti=2;
            else if(tmp.face==t.face) ti=0;
            else ti=1;
            ti++;
            for(int j=0;j<3;j++)
            {
                tmp.x+=fx[i].x;
                tmp.y+=fx[i].y;
                if(tmp.x<1||tmp.y<1||tmp.x>=n||tmp.y>=m) break;
                if(d[tmp.x][tmp.y]||d[tmp.x-1][tmp.y]||d[tmp.x][tmp.y-1]||d[tmp.x-1][tmp.y-1]) break;
                if(tmp.x==st.x&&tmp.y==st.y) continue;
                int temp=ans[t.x][t.y]+ti;
                if(sum&&temp>=sum) break;
                if(!ans[tmp.x][tmp.y]||temp<ans[tmp.x][tmp.y])
                {
                    ans[tmp.x][tmp.y]=temp;
                    if(!v[tmp.x][tmp.y][tmp.face])
                    {
                        v[tmp.x][tmp.y][tmp.face]=true;
                        q.push(tmp);
                    }
                }
            }
        }
    }
}
void set()
{
    fx[0].x=-1,fx[0].y=0;
    fx[1].x=0,fx[1].y=-1;
    fx[2].x=0,fx[2].y=1;
    fx[3].x=1,fx[3].y=0;
    cin>>n>>m;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
            scanf("%d",&d[i][j]);
    cin>>st.x>>st.y>>di.x>>di.y>>dire;
    if(dire=='N') dire=0;
    else if(dire=='W') dire=1;
    else if(dire=='E') dire=2;
    else if(dire=='S') dire=3;
    di.face=st.face=dire;
}
int main()
{
    set();
    if(st==di)
    {
        cout<<0;
        return 0;
    }
    spfa();
    if(ans[di.x][di.y]) cout<<ans[di.x][di.y];
    else cout<<-1;
    return 0;
}
--It's the end.Thanks for your read.--