洛谷题解——P1126：机器人搬重物

题目相关

题目链接

洛谷，https://www.luogu.com.cn/problem/P1126。

题目描述

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

输入格式

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

输出格式

一个整数，表示机器人完成任务所需的最少时间。如果无法到达，输出 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、有方向之分。也就是说机器人只能向当前方向移动。

2、机器人指令：Creep、Walk、Run、Left、Right。

3、机器人是有大小的。题目告诉我们机器人直径有 1.6m，也就是说要考虑这个因素。参考插图，可以看出，当地图某个位置是障碍物，即数据为 1，这个障碍物四周机器人是没法走的。因为每个格子只有 1m 大小，机器人直径有 1.6m。还有一个就是迷宫的边缘机器人没法走。

样例数据分析

注意机器人开始有一个方向，如本题样例方向是 S。所谓的开始方向的含义就是，Creep、Walk 和 Run 这三个指令只能向当前方向运动。其他没什么好写的。省略吧。

编程思路

套用标准 BFS 遍历的模板即可。

代码细节

如何定义方向？

1、我是使用了 C++ 的 enum 类型，定义方法如下：

enum DIR {
 //方向定义 
 EAST = 0,
 SOUTH,
 WEST,
 NORTH
};

使用 enum 只是增加了代码的可读性，其他无卵用。

2、在坐标定义中需要增加方向定义。定义方法如下：

struct POS {
 int x, y;//坐标
 int dir;//方向
 int dis;//距离 
 
};

如何描述机器人指令？

我反正没想出什么方法可以归一化描述。只好用最笨的方法，逐一描述机器人所以指令。伪代码如下：

处理走路的3中方法
处理左转
处理右转

AC 参考代码

#include <cstdio>
#include <queue>

enum DIR {
 //方向定义 
 EAST = 0,
 SOUTH,
 WEST,
 NORTH
};

struct POS {
 int x, y;//坐标
 int dir;//方向
 int dis;//距离 
 
};

const int MAXN = 54;
struct MAZE {
 int row, col;//长宽 
 int x1, y1;//起点 
 int x2, y2;//终点
 int map[MAXN][MAXN];//迷宫数据
 bool visit[MAXN][MAXN][4];//访问性 
 int dir;
};

int bfs(MAZE &maze);

int main() {
 MAZE maze={};
 scanf("%d %d", &maze.row, &maze.col);
 
 int i, j;
 for (i=1; i<=maze.row; i++) {
  for (j=1; j<=maze.col; j++) {
   scanf("%d", &maze.map[i][j]);
   //注意机器人体积 
   if (maze.map[i][j]==1) {
    maze.map[i-1][j]=1;
    maze.map[i][j-1]=1;
    maze.map[i-1][j-1]=1;
   }
  }
 }
 
 char dir;
 scanf("%d %d %d %d %c", &maze.x1, &maze.y1, &maze.x2, &maze.y2, &dir);
 if (dir=='S') {
  maze.dir = SOUTH;
 } else if (dir=='W') {
  maze.dir = WEST;
 } else if (dir == 'N') {
  maze.dir = NORTH;
 } else {
  maze.dir = EAST;
 }
 
 //特别处理 
 if (maze.x2<1||maze.x2>=maze.row||maze.y2<1||maze.y2>=maze.col||maze.map[maze.x2][maze.y2]==1) {
  printf("-1\n");
  return 0;
 }
 
 printf("%d\n", bfs(maze));
 
 return 0;
}

int bfs(MAZE &maze) {
 std::queue<POS> q;
 
 //起点
 POS cur;
 cur.x   = maze.x1;
 cur.y   = maze.y1; 
 cur.dir = maze.dir;
 cur.dis = 0;
 q.push(cur);
 maze.visit[maze.x1][maze.y1][maze.dir] = true;
 
 //开始遍历 
 POS next;
 const int dx[4] = {0,1,0,-1};
 const int dy[4] = {1,0,-1,0};
 //const int dx[4] = {1,0,-1,0};
 //const int dy[4] = {0,1,0,-1};

 int i;
 while (q.empty()!=true) {
  cur = q.front();
  q.pop();
  
  //判断是否终点
  if (cur.x==maze.x2&&cur.y==maze.y2) {
   return cur.dis;
  }
  
  //开始走路
  for (i=1; i<=3; i++) {
   next.x = cur.x + dx[cur.dir]*i;
   next.y = cur.y + dy[cur.dir]*i;
   
   //判断是否在迷宫内
   if (next.x<1||next.x>=maze.row||next.y<1||next.y>=maze.col||maze.map[next.x][next.y]==1)  {
    break;
   } else if (maze.visit[next.x][next.y][cur.dir]==false) {
    maze.visit[next.x][next.y][cur.dir] = true;
    next.dis = cur.dis + 1;
    next.dir = cur.dir;
    q.push(next);
   }
  }
  
  //左转
  next.x = cur.x;
  next.y = cur.y;
  next.dir = cur.dir - 1;
  if (next.dir==-1) {
   next.dir = NORTH;
  }
  if (maze.visit[next.x][next.y][next.dir]==false) {
   maze.visit[next.x][next.y][next.dir] = true;
   next.dis = cur.dis + 1;
   q.push(next);
  }
  
  //右转 
  next.dir = cur.dir + 1;
  if (next.dir==4) {
   next.dir = EAST;
  }
  if (maze.visit[next.x][next.y][next.dir]==false) {
   maze.visit[next.x][next.y][next.dir] = true;
   next.dis = cur.dis + 1;
   q.push(next);
  }
 }
 
 return -1;
}