CSU-1975 机器人搬重物（BFS）

1975: 机器人搬重物

Time Limit: 1 Sec Memory Limit: 128 Mb Submitted: 64 Solved: 10

Description

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

Input

输入的第一行为两个正整数N,M（N,M<=50），下面N行是储藏室的构造，0表示无障碍，1表示有障碍，数字之间用一个空格隔开。接着一行有四个整数和一个大写字母，分别为起始点和目标点左上角网格的行与列，起始时的面对方向（东E，南S，西W，北N），数与数，数与字母之间均用一个空格隔开。终点的面向方向是任意的。

Output

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

Sample Input

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

Sample Output

Hint

Source

机器人搬重物

题意：给你一个图，让你求出机器人从一个点到另一个点需要的最短时间。乍一看就是普通的BFS求最短路问题。但是有很多坑。。。很多坑。。

　　　①首先机器人是在点上，障碍物是格子，也就是说机器人所在的点周围的4个格子都不能有障碍物。而且点和格子的坐标对应关系要弄清楚，最好画个图。

　　　②然后行走分了方向，其实就是bfs多了两个选择，一个左转一个右转。

　　　③走的时候有直走1、2、3步三种方式，需要判断前方有没有障碍。

思路：进行bfs，直接采用优先队列，这样可以确定到达某一点时肯定是最短时间，不会因为转向什么的产生影响。

　　　几个特判的地方要注意：①起点终点一样，0。②起点或终点在不可移动的地方，-1。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
const int maxn=55;
char c;
int a[maxn][maxn],n,m,sx,sy,ex,ey,sd;
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
bool vis[maxn][maxn][5];
struct node
{
    int x,y,d,step;//用d（0、1、2、3、4）表示不同朝向
    bool operator < (const node &a) const{
        return a.step<step;
    }
};
priority_queue<node> q;
//queue<node> q;

bool check(int x,int y)
{
    if(x>=n||y>=m||x<=0||y<=0)
        return false;
    if(a[x][y]==1||a[x+1][y]==1||a[x][y+1]==1||a[x+1][y+1]==1)
        return false;
    return true;
}

void bfs()
{
    memset(vis,false,sizeof(vis));
    node now,next;
    now.x = sx;
    now.y = sy;
    now.d = sd;
    now.step = 0;
    if(!check(sx,sy))
    {
        printf("-1
");
        return ;
    }
    if(!check(ex,ey))
    {
        printf("-1
");
        return ;
    }
    while(!q.empty()) q.pop();
    q.push(now);
    vis[sx][sy][sd] = true;
    while(!q.empty())
    {
        now = q.top();
        q.pop();
        //printf("%d %d %d %d
",now.x,now.y,now.d,now.step);
        if(now.x==ex&&now.y==ey)
        {
            printf("%d
",now.step);
            return ;
        }
        for(int step=1;step<=3;step++)
        {
            next.x = now.x+dx[now.d]*step;
            next.y = now.y+dy[now.d]*step;
            next.d = now.d;
            if(check(next.x,next.y)&&vis[next.x][next.y][next.d]==false)
            {
                next.step = now.step+1;
                q.push(next);
                vis[next.x][next.y][next.d] = true;
            }
            else//如果1 2 3某一个不能走，那后面的肯定不能走
            {
                break;
            }
        }
        if(vis[now.x][now.y][(now.d+1)%4]==false)//ÓÒ×ª
        {
            next.x = now.x;
            next.y = now.y;
            next.d = (now.d+1)%4;
            next.step = now.step+1;
            q.push(next);
            vis[next.x][next.y][next.d] = true;
        }
        if(vis[now.x][now.y][(now.d-1+4)%4]==false)//×ó×ª
        {
            next.x = now.x;
            next.y = now.y;
            next.d = (now.d-1+4)%4;
            next.step = now.step+1;
            q.push(next);
            vis[next.x][next.y][next.d] = true;
        }
    }
    printf("-1
");
}
int main()
{
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                scanf("%d
",&a[i][j]);
            }
        }
        scanf("%d %d %d %d",&sx,&sy,&ex,&ey);
        getchar();
        scanf("%c",&c);
        if(sx==ex&&sy==ey)
        {
            printf("0
");
            continue;
        }
        if(c=='E') sd=0;
        else if(c=='S') sd=1;
        else if(c=='W') sd=2;
        else if(c=='N') sd=3;
        bfs();
    }
}