P1126 [CERC1996] 机器人搬重物
我理解的题目意思
一个 N×M 的网格，有些格子为不可移动的障碍。机器人的中心总是在格点上，机器人必须在最短的时间内从起点到终点。机器人接受的指令有：
- 向前移动 1 步（
Creep）； - 向前移动 2 步（
Walk）； - 向前移动 3 步（
Run）； - 向左转（
Left）； - 向右转（
Right）。
每个指令所需要的时间为 1 秒。要求机器人完成任务所需的最少时间，若不能完成则输出-1。
$$1≤N,M≤50$$解题思路
输入
第一行为两个正整数 N,M，下面 N 行是储藏室的构造，0 表示无障碍，1 表示有障碍，数字之间用一个空格隔开。接着一行有 4 个整数和 1 个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东 E，南 S，西 W，北 N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。
处理输入：输入可以视为为网格的右下角坐标是否障碍，搜索需要网格点的网络是否障碍，这需要一个转换。因为一个障碍产生4个障碍网格点，机器人无法到边界，故扩充网格 N×M 到网格点网络 N+1×M+1，障碍的左上、上、左的点均为障碍点（包括自己）。
每次的操作
主体使用BFS进行搜索，考虑每次移动方向的变换：可以分为2部分先后考虑即换向、前进。
- 换向
在结构体中设置t记录当前方向，有4个方向可以选择：
fx[5] = {0, -1, 1, 0, 0} fy[5] = {0, 0, 0, -1, 1}
方向按NSWE的顺序对应上下左右和1234，按只有顺时针旋转来考虑：
ft[5] = {0, 1, 4, 2, 3}
实际上有逆时针旋转，故改变4个方向需要时间：
abc[5] = {0, 1, 2, 1, 0}
辅助数组用于逻辑上对齐1234方向的顺序（转i次）：
fft[5] = {0, 1, 3, 4, 2} + i -> ft[5]
- 前进
做123步进的遍历，若遍历到更短时间到达的点则计算后放入队列进行下一次搜索。
代码：
#include <iostream>
#include <cstring>
#include <queue>
#include<cmath>
#include <algorithm>
using namespace std;
int sd[55][55];
int a[55][55];
int m, n;
int x11, y11;
int x2, y2;
int f[55][55];
int fx[5] = {0, -1, 1, 0, 0};
int fy[5] = {0, 0, 0, -1, 1};
int ft[5] = {0, 1, 4, 2, 3};
int fft[5] = {0, 1, 3, 4, 2};
int abc[5] = {0, 1, 2, 1, 0};
struct node
{
int x, y, t, time;
};
queue<node> q;
string ch;
int cto;
void fxto()
{
switch (ch[0])
{
case 'N':
cto = 1;
break;
case 'S':
cto = 2;
break;
case 'W':
cto = 3;
break;
case 'E':
cto = 4;
break;
}
}
void change()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
if (sd[i][j] == 1)
{
a[i - 1][j] = a[i - 1][j - 1] = a[i][j] = a[i][j - 1] = 1;
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
cin >> sd[i][j];
}
}
cin >> x11 >> y11 >> x2 >> y2;
cin >> ch;
fxto();
change();
node first;
first.x = x11;
first.y = y11;
first.t = cto;
first.time = 0;
q.push(first);
node u, d;
while (!q.empty())
{
u = q.front();
q.pop();
for (int i = 1; i <= 4; i++)
{
int turn = abc[i];
int dir = fft[u.t] + i;
if (dir >= 5 && dir <= 8)
dir -= 4;
dir = ft[dir];
for (int j = 1; j <= 3; j++)
{
int lsx = u.x + fx[dir] * j;
int lsy = u.y + fy[dir] * j;
if (lsx <= 0 || lsx >= n || lsy <= 0 || lsy >= m || (lsx == x11 && lsy == y11) || a[lsx][lsy] == 1)
{
break;
}
if ((u.time + turn + 1 < f[lsx][lsy] || f[lsx][lsy] == 0) && a[lsx][lsy] == 0)
{
d.x = lsx;
d.y = lsy;
d.t = dir;
d.time = u.time + turn + 1;
f[lsx][lsy] = d.time;
q.push(d);
}
}
}
}
if (f[x2][y2] == 0 && (x11 != x2 || y11 != y2))
{
cout << "-1";
}
else
cout << f[x2][y2];
return 0;
}
注意：若使用全局变量y1 ，则与
- 参考 雒仁韬