[luogu p1126] 机器人搬重物

传送门

题面

题目描述

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

输入输出格式

输入格式

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

输出格式

一个整数,表示机器人完成任务所需的最少时间。如果无法到达,输出\(-1\)[luogu p1126] 机器人搬重物

输入输出样例

输入样例 #1

0 0 0 0 1 0 0 0
0 0 0 0 0 0 1 0
0 1 0 0 0 0 0 0
1 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 1 0 0 0 0
0 1 1 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
2 7 S

输出样例 #1

12

分析

这道题一看就是个广搜,思维没有难度,但是细节确实很多,需要注意的是:

  • 障碍物在格子上,机器人在格点上。
  • 机器人有直径,所以不可以活动到储藏室的外围部分。实际的一个障碍物会导致机器人的中心有四个点不可取,不只是一个,还有障碍物的四个角。
  • 向前走的时候,如果遇到墙,我们应该 立刻break循环,停止一步到三步的枚举,而不是continue 因为continue会导致机器人在接下来的循环中可能会穿墙而走,现实中这当然不可取。
  • 机器人在旋转时也需要1s的时间。
  • 记忆化搜索的时候,我们会有一个标记数组vis,我一开始想的是读到障碍物就把四个点的vis数组标记为true,但是在实际编码中我发现了这样存在的问题,刚才说了,如果遇到墙,我们应该 立刻break循环,停止一步到三步的枚举,而不是continue 但是已经访问的点却不一定要这样,这一点需注意。如果样例的输出是7,很可能就是如此导致的。

分析完这么多细节,是时候上代码了。

代码

广搜,bfs

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <queue>

int n,m;
int startx,starty,endx,endy,dir;
bool vis[20005];
int state[55][55];
const int dx[] = {-1,0,1,0};
const int dy[] = {0,1,0,-1};

struct node{
    int x,y,d,step;
};

std :: queue <node> q;

int getkey(int x,int y,int dir){
    return dir * 2500 + x * 50 + y;
}//这就保证了每一个x,y在dir方向上都有一个对应的key,便于记忆化。

bool valid(int x,int y,int dir){
    if(x <= 0 || y <= 0 || x >= n || y >= m || state[x][y] ||
                state[x+1][y] ||
                state[x+1][y+1] ||
                state[x][y+1]) return false;
    return true;
}//判断是否超出边界,或者是有没有墙

void bfs(){
    switch(dir){
        case 'N': dir = 0; break;
        case 'E': dir = 1; break;
        case 'S': dir = 2; break;
        case 'W': dir = 3; break;
        default: dir = 10086; break;
    }

    node now;
    now.x = startx;
    now.y = starty;
    now.d = dir;
    now.step = 0;
    q.push(now);

    while(!q.empty()){
        now = q.front();
        q.pop();
        int nowx = now.x;
        int nowy = now.y;
        int dir = now.d;
        //printf("%d %d %d \n",nowx,nowy,dir);
        int key = getkey(nowx,nowy,dir);
        if(nowx == endx && nowy == endy){
            printf("%d\n",now.step);
            exit(0);
        }
        //std :: cout << "Getting key done:"<<key << std :: endl;
        if(vis[key]) continue;
        vis[key] = true;
        //这两句是记忆化的部分。
        
        node nxt;
        nxt.step = now.step + 1;
        int nxtx = now.x;
        int nxty = now.y;
        nxt.x = nxtx;
        nxt.y = nxty;
        nxt.d = (dir + 3) % 4;
        q.push(nxt);
        nxt.d = (dir + 5) % 4;
        q.push(nxt);

        nxt.d = dir;
        for(int i = 1; i <= 3; i++){
            nxtx = nowx + dx[dir] * i;
            nxty = nowy + dy[dir] * i;
            if(!valid(nxtx,nxty,dir)) break;//千万不能是continue,原因刚刚说了
            nxt.x = nxtx;
            nxt.y = nxty;
            q.push(nxt);
        }
    }

    printf("-1\n");
    return ;
}

int main(){
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            scanf("%d",&state[i][j]);
            if(!state[i][j]) continue;
            for(int dir = 0; dir <= 3; dir++){
                state[i][j] = true;
                state[i+1][j] = true;
                state[i+1][j+1] = true;
                state[i][j+1] = true;
            }
        }
    scanf("%d %d %d %d %c",&startx,&starty,&endx,&endy,&dir);
    bfs();
    return 0;
}

评测结果

AC 100R30912296

over.