思路
题意有点坑。。
只有一个地方用了米
的描述,其他地方全都是步
,所以导致无法透彻理解题意。
看了题解才明白不能走最外侧的格子,因为机器人有宽度(大雾,你也没说格子的边长啥的啊,题意太不准确了吧……
一个坑点就是机器人走的是格点,而障碍是格子,格子的四个点都不能走。
还有就是第一次访问这个点并不一定是访问这个点的最小路径,因为最多可以走三步(调了很久……),所以可以记一个 \(dis\) 数组,如果目前的步数小于到当前点的 \(dis\),一样应该加入队列中。
注意走 \(1,2,3\) 步的花费都是 \(1\),想达到自己想转到的方向的最大花费其实是 \(2\)。
(写了个一百多行的大暴搜啊)
代码
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 66;
const int dx[13] = {0, -1, 0, 1, 0, -2, 0, 2, 0, -3, 0, 3, 0};
const int dy[13] = {0, 0, 1, 0, -1, 0, 2, 0, -2, 0, 3, 0, -3};
const int diss[5][5] = {{0,0,0,0,0},{0,0,1,2,1},{0,1,0,1,2},{0,2,1,0,1},{0,1,2,1,0}};
inline int read() {
char c = getchar(); int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, a[A][A], dis[A][A], ans = 0x3f3f3f3f;
int sx, sy, tx, ty, sdir, vis[A][A];
struct node { int x, y, dir, cnt; };
inline void bbffss() {
queue <node> Q;
memset(dis, 0x3f, sizeof(dis));
Q.push((node){sx, sy, sdir, 0});
dis[sx][sy] = 0, vis[sx][sy] = 1;
while (!Q.empty()) {
node tmp = Q.front(); Q.pop();
int x = tmp.x, y = tmp.y, cnt = tmp.cnt, dir = tmp.dir;
if (x == tx && y == ty) {
ans = min(ans, cnt);
continue;
}
for (int i = 1; i <= 12; i++) {
int bx = x + dx[i], by = y + dy[i];
int nowdir = (i % 4);
if (nowdir == 0) nowdir = 4;
int change = diss[dir][nowdir];
if (i >= 1 && i <= 4) {
if (bx >= 1 && bx <= n && by >= 1 && by <= m && (!vis[bx][by] || cnt + 1 + change < dis[bx][by]) && a[bx][by] != 1) {
Q.push((node){bx, by, nowdir, cnt + 1 + change});
dis[bx][by] = cnt + 1 + change, vis[bx][by] = 1;
}
}
else if (i >= 5 && i <= 8) {
int flag = 0;
if (x != bx) {
int minn = min(x, bx), maxn = max(x, bx);
for (int k = minn; k <= maxn; k++) {
if (a[k][by]) { flag = 1; break; }
}
}
if (y != by) {
int minn = min(y, by), maxn = max(y, by);
for (int k = minn; k <= maxn; k++) {
if (a[bx][k]) { flag = 1; break; }
}
}
if (flag) continue;
if (bx >= 1 && bx <= n && by >= 1 && by <= m && (!vis[bx][by] || cnt + 1 + change < dis[bx][by])) {
Q.push((node){bx, by, nowdir, cnt + 1 + change});
dis[bx][by] = cnt + 1 + change, vis[bx][by] = 1;
}
}
else if (i >= 9 && i <= 12) {
int flag = 0;
if (x != bx) {
int minn = min(x, bx), maxn = max(x, bx);
for (int k = minn; k <= maxn; k++){
if (a[k][by]) { flag = 1; break; }
}
}
if (y != by) {
int minn = min(y, by), maxn = max(y, by);
for (int k = minn; k <= maxn; k++){
if (a[bx][k]) { flag = 1; break; }
}
}
if (flag) continue;
if (bx >= 1 && bx <= n && by >= 1 && by <= m && (!vis[bx][by] || cnt + 1 + change < dis[bx][by])) {
Q.push((node){bx, by, nowdir, cnt + 1 + change});
dis[bx][by] = cnt + 1 + change, vis[bx][by] = 1;
}
}
}
}
}
int main() {
n = read(), m = read();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
a[i][j] = read();
if (a[i][j] == 1)
a[i - 1][j - 1] = 1, a[i - 1][j] = 1, a[i][j - 1] = 1;
}
}
for (int i = 1; i <= n; i++) a[i][0] = a[i][m] = 1;
for (int i = 0; i <= m; i++) a[0][i] = 1, a[n][i] = 1;
sx = read(), sy = read(), tx = read(), ty = read();
char s;
cin >> s;
if (s == 'N') sdir = 1;
else if (s == 'E') sdir = 2;
else if (s == 'S') sdir = 3;
else if (s == 'W') sdir = 4;
bbffss();
printf("%d", ans == 0x3f3f3f3f ? -1 : ans);
return 0;
}