洛谷P1126 机器人搬重物【bfs】

时间:2024-07-14 19:34:02

题目链接https://www.luogu.org/problemnew/show/P1126

题意:

给定一个n*m的方格,机器人推着直径是1.6的球在格子的线上运动。

每一秒钟可以向左转,向右转或者直走1步2步或是3步。

现在给定一个起点和开始的朝向,问走到终点至少要多少时间。

思路:

真是一道*坑题。题目给出的是格点,而机器人是在交点上运动的。

盗用一下洛谷@雒仁韬的图。题目给出的障碍物其实是橙色的四个点中的右下角的这个。

而且由于球的直径,最外围边界并不能走到。如果正确理解了题意的话应该就没问题了。

洛谷P1126 机器人搬重物【bfs】

由于有方向,所以用三维数组来存某点是否被访问。

 #include<stdio.h>
#include<stdlib.h>
#include<map>
#include<set>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue> using namespace std; int n, m;
int mat[][];
//0E, 1S, 2W, 3N
int dx[][] = {{, , }, {, , }, {, , }, {-, -, -}};
int dy[][] = {{, , }, {, , }, {-, -, -}, {, , }};
bool vis[][][];
struct node{
int x, y;
int dir;
int t;
}st, ed; int getdir(char c)
{
if(c == 'E')return ;
if(c == 'S')return ;
if(c == 'W')return ;
if(c == 'N')return ;
} bool check(int i, int j)
{
return (i >= && i < n && j >= && j < m);
} int main()
{
scanf("%d%d", &n, &m);
for(int i = ; i <= n; i++){
for(int j = ; j <= m; j++){
scanf("%d", &mat[i][j]);
if(mat[i][j]){
mat[i - ][j] = ;
mat[i][j - ] = ;
mat[i - ][j - ] = ;
}
}
} scanf("%d%d%d%d", &st.x, &st.y, &ed.x, &ed.y);
char dir;
//st.x--;st.y--;ed.x--;ed.y--;
getchar();
scanf("%c", &dir);
st.dir = getdir(dir);
st.t = ; queue<node>que;
que.push(st);
vis[st.x][st.y][st.dir] = true;
int ans = -;
while(!que.empty()){
node now = que.front();que.pop();
//cout<<endl<<now.x<<" "<<now.y<<" "<<now.t<<endl;
if(now.x == ed.x && now.y == ed.y){
ans = now.t;
break;
}
node to;
to.x = now.x;to.y = now.y;to.t = now.t + ;
to.dir = (now.dir + ) % ;
if(!vis[to.x][to.y][to.dir]){
vis[to.x][to.y][to.dir] = true;
que.push(to);
}
to.dir = (now.dir - + ) % ;
if(!vis[to.x][to.y][to.dir]){
vis[to.x][to.y][to.dir] = true;
que.push(to);
} to.dir = now.dir;
for(int i = ; i < ; i++){
to.x = now.x + dx[to.dir][i];
to.y = now.y + dy[to.dir][i];
if(mat[to.x][to.y])break;
if(check(to.x, to.y) && !vis[to.x][to.y][to.dir]){
vis[to.x][to.y][to.dir] = true;
que.push(to);
//cout<<to.x<<" "<<to.y<<" "<<to.t<<endl;
}
}
} cout<<ans<<endl; return ;
}