洛谷 P1126 机器人搬重物

时间：2022-06-17 00:46:52


第n个令我重写的洛谷题

题目描述

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

输入格式

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

输出格式

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

洛谷 P1126 机器人搬重物

输入输出样例

输入

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

输出

12

心酸历程

洛谷 P1126 机器人搬重物

　

　　起初审题没考虑题目数据较大 直接用了深度优先搜索解题 各种TLE超时

　　再来　四个转向　三种步数　思路有点乱　调试了很长时间

AC代码

#include<iostream>
#include<queue>
using namespace std;
struct zb {
  int x;
  int y;
  char d;
  int step;//一共的步数
};
queue<zb> que;
int N, M;
int sta_x, sta_y, end_x, end_y;
char dir;
int Dir[4][2] = { 1,0,0,1,-1,0,0,-1 };//下，右，上，左
int _map[53][53];
int map[53][53];
int visit[53][53][4];

//ans函数 由已知直线求出最短步数
int ans(int n)
{
  int anser = 0;
  int a = n / 3;
  int yu = n % 3;
  anser += a;
  a = yu / 2;
  yu = yu % 2;
  anser += a;
  anser += yu;
  return anser;
}

//判断该位置是否经过
bool bo(zb a)
{
  int c;    //当前位置状态 四个方向
  if (a.d == 'S')c = 0;
  if (a.d == 'N')c = 1;
  if (a.d == 'W')c = 2;
  if (a.d == 'E')c = 3;
  if (map[a.x][a.y] == 1 || visit[a.x][a.y][c] == 1 || a.x <= 0 || a.y <= 0 || a.x >= N || a.y >= M)
    return false;
  return true;
}
//广搜
void bfs() {
  while (!que.empty())
  {
    //得到队头结点信息
    int x0 = que.front().x;
    int y0 = que.front().y;
    char d0 = que.front().d;
    int step = que.front().step;

    //标记经过的点
    int a = -1;
    if (d0 == 'S')a = 0;
    if (d0 == 'N')a = 1;
    if (d0 == 'W')a = 2;
    if (d0 == 'E')a = 3;
    visit[x0][y0][a] = 1;


    //到达 输出结果并退出
    if (x0 == end_x && y0 == end_y)
    {
      cout << step;
      return;
    }

    //四种方向情况  入队操作
    if (d0 == 'S')
    {
      //方向一致 三种步数
      zb dq1;
      dq1.x = x0 + 1; dq1.y = y0; dq1.step = step + 1; dq1.d = 'S';
      if (bo(dq1))
        que.push(dq1);
      zb dq2;
      dq2.x = x0 + 2; dq2.y = y0; dq2.step = step + 1; dq2.d = 'S';
      if (bo(dq1) && bo(dq2))
        que.push(dq2);
      zb dq3;
      dq3.x = x0 + 3; dq3.y = y0; dq3.step = step + 1; dq3.d = 'S';
      if (bo(dq1) && bo(dq2) && bo(dq3))
        que.push(dq3);

      //方向不同 两种转向
      zb dq;
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'E';
      if (bo(dq))
        que.push(dq);
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'W';
      if (bo(dq))
        que.push(dq);
    }
    if (d0 == 'N')
    {
      zb dq1;
      dq1.x = x0 - 1; dq1.y = y0; dq1.step = step + 1; dq1.d = 'N';
      if (bo(dq1))
        que.push(dq1);
      zb dq2;
      dq2.x = x0 - 2; dq2.y = y0; dq2.step = step + 1; dq2.d = 'N';
      if (bo(dq1) && bo(dq2))
        que.push(dq2);
      zb dq3;
      dq3.x = x0 - 3; dq3.y = y0; dq3.step = step + 1; dq3.d = 'N';
      if (bo(dq1) && bo(dq2) && bo(dq3))
        que.push(dq3);
      zb dq;
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'E';
      if (bo(dq))
        que.push(dq);
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'W';
      if (bo(dq))
        que.push(dq);
    }
    if (d0 == 'W')
    {
      zb dq1;
      dq1.x = x0; dq1.y = y0 - 1; dq1.step = step + 1; dq1.d = 'W';
      if (bo(dq1))
        que.push(dq1);
      zb dq2;
      dq2.x = x0; dq2.y = y0 - 2; dq2.step = step + 1; dq2.d = 'W';
      if (bo(dq1) && bo(dq2))
        que.push(dq2);
      zb dq3;
      dq3.x = x0; dq3.y = y0 - 3; dq3.step = step + 1; dq3.d = 'W';
      if (bo(dq1) && bo(dq2) && bo(dq3))
        que.push(dq3);
      zb dq;
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'N';
      if (bo(dq))
        que.push(dq);
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'S';
      if (bo(dq))
        que.push(dq);
    }
    if (d0 == 'E')
    {
      zb dq1;
      dq1.x = x0; dq1.y = y0 + 1; dq1.step = step + 1; dq1.d = 'E';
      if (bo(dq1))
        que.push(dq1);
      zb dq2;
      dq2.x = x0; dq2.y = y0 + 2; dq2.step = step + 1; dq2.d = 'E';
      if (bo(dq1) && bo(dq2))
        que.push(dq2);
      zb dq3;
      dq3.x = x0; dq3.y = y0 + 3; dq3.step = step + 1; dq3.d = 'E';
      if (bo(dq1) && bo(dq2) && bo(dq3))
        que.push(dq3);
      zb dq;
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'N';
      if (bo(dq))
        que.push(dq);
      dq.x = x0; dq.y = y0; dq.step = step + 1; dq.d = 'S';
      if (bo(dq))
        que.push(dq);
    }
    que.pop();
  }
  cout << -1 << endl;
}
int main()
{   //输入
  cin >> N >> M;
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
      cin >> _map[i][j];
  cin >> sta_x >> sta_y >> end_x >> end_y;
  cin >> dir;
  //重新构图  初始化map数组
  for (int i = 0; i < N; i++)
    for (int j = 0; j < M; j++)
    {
      if (_map[i][j] == 1)
      {
        map[i][j] = 1;
        map[i][j + 1] = 1;
        map[i + 1][j] = 1;
        map[i + 1][j + 1] = 1;
      }
    }

  //完善初始位置结点 并入队
  zb st;
  st.x = sta_x; st.y = sta_y;
  st.d = dir;
  st.step = 0;
  que.push(st);

  //广搜
  bfs();
  system("pause");
  return 0;
}

洛谷 P1126 机器人搬重物


标签：

相关文章