🎈 原创

洛谷P1126 机器人搬重物

题目描述

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

输入格式

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

输出格式

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

输入输出样例

输入 #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

---

分析

这道题我真的是快要写吐了，踩了所有的坑。。。这道题写了几乎大半天才AC，今天不想再写题了。

题目的意思很明确，就是用BFS，但是就是要你注意细节。

1. 注意前进的方式

机器人可以最多一次前进3格，但是要注意如果前进的路上有障碍就不能前进，不能跨过障碍！！我第一次也就是考试的时候踩在了这个坑上，想了很久没想明白为什么样例都过不了。

2. 注意什么时候记录访问标记

一般的BFS是在入队的时候就做一个已访问的标记，这样可以防止对同一节点的重复访问。但是这道题要在出对的时候做访问标记。就是这个点浪费了我几个小时！

对于这一组数据

17 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 1 0 1 0 1 0 1 0 1 0 0 1 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16 4 4 16 N

正确答案是

12

但是用入队标记时得到的结果是13，很显然不是最优，至于这是为什么，由于我本人脑子水平实在有限，想了几个小时还是不能确切的理解，网上也没有对此具体的解释。我自己的想法是这样的：

我用两种颜色画了一下路线，红色是入队标记得到13的路线，蓝色是出队标记得到12的路线。
因为我的算法中路线的判断是把前进1到3格符合的点全部入队，而此时会将这几个点全部标记为已访问，这样就导致了如果更短的路线在这几个点上有重叠的路线，就无法继续前进，从而导致正确路线被舍弃，所以这题不能用入队标记，只能牺牲一下有重复的点入队来保证正确的路线不会被屏蔽。

代码

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

int N, M;
int board[100][100] = {0};
bool vis[100][100][4] = {false};

//struct check
//{
//    int x, y, dir;
//};

struct pos
{
    int x, y;
    int dir;
    int cost = 0;
//    vector<check> path;
};
pos Start, End;
int X[4] = {0, 1, 0, -1}, Y[4] = {1, 0, -1, 0};

void init();
bool judge(pos temp);
int BFS();

int main(int argc, const char * argv[])
{
    init();


    //vis[Start.x][Start.y][Start.dir] = true;
    cout << BFS() << endl;

//    for(int i = 0; i < N; i++)
//    {
//        for(int j = 0; j < M; j++)
//            cout << board[i][j] << " ";
//        cout << endl;
//    }

    return 0;
}

void init()
{
    cin >> N >> M;
    for(int i = 0; i < N; i++)
        for(int j = 0; j < M; j++)
        {
            int temp;
            cin >> temp;
            if(temp == 1)
            {
                board[i][j] = 1;
                board[i][j + 1] = 1;
                board[i + 1][j] = 1;
                board[i + 1][j + 1] = 1;
            }
        }
    N += 1; M += 1;
    for(int i = 0; i < N; i++)
        board[i][0] = board[i][M - 1] = 1;
    for(int i = 0; i < M; i++)
        board[0][i] = board[N - 1][i] = 1;
    cin >> Start.x >> Start.y;
    cin >> End.x >> End.y;
    char ch;
    cin >> ch;
    if(ch == 'E') Start.dir = 0;
    else if(ch == 'S') Start.dir = 1;
    else if(ch == 'W') Start.dir = 2;
    else if(ch == 'N') Start.dir = 3;
    Start.cost = 0;


//    check t;
//    t.x = Start.x; t.y = Start.y; t.dir = Start.dir;
//    Start.path.push_back(t);

}

bool judge(pos temp)
{
    if(vis[temp.x][temp.y][temp.dir] || temp.x < 0 || temp.x >= N || temp.y < 0 || temp.y >= M
    || board[temp.x][temp.y] == 1)
        return false;
    else
        return true;
}

int BFS()
{
    queue<pos> Q;
    Q.push(Start);
    while(!Q.empty())
    {
        pos now = Q.front();
        Q.pop();
        if(vis[now.x][now.y][now.dir])
            continue;
        vis[now.x][now.y][now.dir] = true;

//        for(int i = 0; i < now.path.size(); i++)
//            cout << now.path[i].x << " " << now.path[i].y << " " << now.path[i].dir << " -> ";
//        cout << endl;

        if(now.x == End.x && now.y == End.y)
        {
            return now.cost;
        }
        for(int i = 1; i <= 3; i++)
        {
            pos temp;
            temp.x = now.x + X[now.dir] * i;
            temp.y = now.y + Y[now.dir] * i;
            temp.dir = now.dir;
            temp.cost = now.cost + 1;
            if(judge(temp))
            {
//                temp.path = now.path;
//
//                check t;
//                t.x = temp.x; t.y = temp.y; t.dir = temp.dir;
//                temp.path.push_back(t);
//                cout << t.x << " " << t.y << " " << t.dir << endl;

                Q.push(temp);
                //vis[temp.x][temp.y][temp.dir] = true;
            }
            else
                break;
        }
        pos temp;
        temp.x = now.x; temp.y = now.y;
        temp.cost = now.cost + 1;
        temp.dir = (now.dir + 1) % 4;
        if(judge(temp))
        {
//            temp.path = now.path;
//            check t;
//            t.x = temp.x; t.y = temp.y; t.dir = temp.dir;
//            temp.path.push_back(t);
//            cout << t.x << " " << t.y << " " << t.dir << endl;

            Q.push(temp);
            //vis[temp.x][temp.y][temp.dir] = true;
        }
        temp.dir = (now.dir + 3) % 4;
        if(judge(temp))
        {
//            temp.path = now.path;
//            check t;
//            t.x = temp.x; t.y = temp.y; t.dir = temp.dir;
//            temp.path.push_back(t);
//            cout << t.x << " " << t.y << " " << t.dir << endl;

            Q.push(temp);
            //vis[temp.x][temp.y][temp.dir] = true;
        }

    }

    return -1;
}

代码实在是太脏乱了，因为我写了很多的输出调试，来看到底是怎么走的。也懒得删了，不想碰这段代码了，再宁马的见。