Skip to content

14212: 【原4212】机器人搬重物

题目

题目描述

author: Ge Yan 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4212

Description

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

hint

Input Format

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

Output Format

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

Sample Input

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

Sample Output

12

zqy2018's solution

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
struct node{
    int x, y, to;
    node(int _x, int _y, int _t):
        x(_x), y(_y), to(_t){}
    node(){}
};
node q[100005];
int n, m, ma[55][55] = {0};
int rear = 0, front = 0;
int st[2], ls[2];                                       // start point and destination
const int dx[] = {-1, 0, 0, 1}, dy[] = {0, 1, -1, 0};   //N0 S3 W2 E1
int dis[55][55][4];
char dir;
inline void enque(int a, int b, int c){
    q[rear++] = node(a, b, c);
}
int bfs(){
    int dir_id;
    if (dir == 'N') dir_id = 0;
    if (dir == 'S') dir_id = 3;
    if (dir == 'E') dir_id = 1;
    if (dir == 'W') dir_id = 2;
    dis[st[0]][st[1]][dir_id] = 0;
    enque(st[0], st[1], dir_id);
    while (rear > front){
        int cx = q[front].x;
        int cy = q[front].y;
        int cd = q[front++].to;
        int step = dis[cx][cy][cd];
        for (int i = 0; i < 4; ++i)
            if (cd != i && cd + i != 3 && dis[cx][cy][i] == 0x3f3f3f3f)
                dis[cx][cy][i] = step + 1, enque(cx, cy, i); 
        for (int i = 0; i < 3; ++i){
            cx += dx[cd], cy += dy[cd];
            if (cx <= 0 || cy <= 0 || cx >= n || cy >= m)
                break;
            if (ma[cx][cy]) break;  // keypoint
            if (dis[cx][cy][cd] < 0x3f3f3f3f) continue;
            dis[cx][cy][cd] = step + 1, enque(cx, cy, cd);
        } 
    }
    int res = 0x3f3f3f3f;
    for (int i = 0; i < 4; ++i)
        res = min(res, dis[ls[0]][ls[1]][i]);
    return res;
}
int main(){
    scanf("%d%d", &n, &m);
    memset(dis, 0x3f, sizeof(dis));
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= m; ++j){
            int t;
            scanf("%d", &t);
            if(t)
                ma[i][j] = ma[i - 1][j - 1] = ma[i - 1][j] = ma[i][j - 1] = 1;
        }
    }
    scanf("%d%d%d%d %c", &st[0], &st[1], &ls[0], &ls[1], &dir);
    if (ma[st[0]][st[1]] || ma[ls[0]][ls[1]]){
        printf("-1\n");
        return 0;
    }    
    int ans = bfs();
    printf("%d\n", (ans < 0x3f3f3f3f ? ans: -1));
    return 0;    
}