poj 1367 robot(搜索)

题意：给你一个图，求起点到终点的最少时间

每次有两种选择①：往前走1~3步 ②原地选择90° 费时皆是1s

图中1为障碍物，而且不能出边界。还要考虑机器人的直径

思路：

bfs，但是在判断时出了点问题/(ㄒoㄒ)/，想复杂了，导致一直wr。

用vis[x][y][dir] 表示状态，即在(x,y)点的dir方向

问题：

①考虑判断条件时出现问题，开始想得太简单，后来想得太复杂= =

②最开始写的搜索部分太乱

③题意理解不准确。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
#include <queue>
#include <algorithm>
typedef long long ll;
using namespace std;

int tmap[60][60];
int vis[60][60][5];
struct node
{
    int x,y;
    int step;
    int dir;
};
int n,m;
char to[10];
int fx,fy,tx,ty;
int dir[5][2] = {{-1,0},{0,1},{1,0},{0,-1}};
int ans = -1;

bool judge(node a)              //判断当前是否包含了黑点
{
    if(a.x<1||a.x>=n||a.y<1||a.y>=m)
        return false;
    if(tmap[a.x][a.y]||tmap[a.x+1][a.y]||tmap[a.x][a.y+1]||tmap[a.x+1][a.y+1])
        return false;
    return true;
}

void bfs()
{
    queue<node>q;

    node cur;
    ans = -1;
    cur.x = fx;
    cur.y = fy;
    cur.step = 0;

    if(to[0] == 's') cur.dir = 2;
    if(to[0] == 'n') cur.dir = 0;
    if(to[0] == 'w') cur.dir = 3;
    if(to[0] == 'e') cur.dir = 1;
    vis[cur.x][cur.y][cur.dir] = 1;
    q.push(cur);
    while(!q.empty())
    {
        cur = q.front();
        q.pop();
//        printf("%d %d %d %d
",cur.x,cur.y,cur.dir,cur.step);
        for(int i = 1; i <= 3; i++)
        {
            node t;
            int dr = cur.dir;
            t.dir = cur.dir;
            t.x = cur.x + dir[dr][0]*i;
            t.y = cur.y + dir[dr][1]*i;
            t.step = cur.step+1;
            if(!judge(t))
                break;
            if(t.x == tx  &&  t.y == ty)
            {
                ans = t.step;
//                printf("%d %d %d
",t.x,t.y,t.dir);
                return ;
            }
            if(!vis[t.x][t.y][t.dir])
            {
                vis[t.x][t.y][t.dir] = 1;
                q.push(t);
            }
        }
        for(int i = 0; i < 4; i++)
        {
            if(max(i,cur.dir)-min(i,cur.dir) == 2)
                continue;
            if(vis[cur.x][cur.y][i])
                continue;
            node t = cur;
            t.dir = i;
            t.step = cur.step+1;
            vis[t.x][t.y][t.dir] = 1;
            q.push(t);
        }
    }
    return ;
}

int main()
{
    while(scanf("%d%d",&n,&m) != EOF)
    {
        if(n == 0 && m == 0)
            break;
        memset(vis,0,sizeof(vis));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= m; j++)
            {
                scanf("%d",&tmap[i][j]);
            }
        scanf("%d%d%d%d",&fx,&fy,&tx,&ty);
        scanf("%s",to);
        if(tmap[tx][ty])
        {
            printf("-1
");
            continue;
        }
        if(fx == tx && fy == ty)
        {
            printf("0
");
            continue;
        }
        bfs();

        if(ans == -1)
            printf("-1
");
        else
            printf("%d
",ans);
    }
    return 0;
}

相关推荐