洛谷P1126 机器人搬重物【bfs】-程序员宅基地

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

题意：

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

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

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

思路：

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

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

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

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

 

#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[55][55];
//0E, 1S, 2W, 3N
int dx[4][3] = {
    {
    0, 0, 0}, {
    1, 2, 3}, {
    0, 0, 0}, {-1, -2, -3}};
int dy[4][3] = {
    {
    1, 2, 3}, {
    0, 0, 0}, {-1, -2, -3}, {
    0, 0, 0}};
bool vis[55][55][5];
struct node{
    int x, y;
    int dir;
    int t;
}st, ed;

int getdir(char c)
{
    if(c == 'E')return 0;
    if(c == 'S')return 1;
    if(c == 'W')return 2;
    if(c == 'N')return 3;
}

bool check(int i, int j)
{
    return (i >= 1 && i < n && j >= 1 && j < m);
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            scanf("%d", &mat[i][j]);
            if(mat[i][j]){
                mat[i - 1][j] = 1;
                mat[i][j - 1] = 1;
                mat[i - 1][j - 1] = 1;
            }
        }
    }
    
    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 = 0;
    
    queue<node>que;
    que.push(st);
    vis[st.x][st.y][st.dir] = true;
    int ans = -1;
    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 + 1;
        to.dir = (now.dir + 1) % 4;
        if(!vis[to.x][to.y][to.dir]){
            vis[to.x][to.y][to.dir] = true;
            que.push(to);
        }
        to.dir = (now.dir - 1 + 4) % 4;
        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 = 0; i < 3; 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 0;
}