题意:给你一个图,求起点 到 终点的最少时间
每次有两种选择①:往前走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\n",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\n",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\n");
continue;
}
if(fx == tx && fy == ty)
{
printf("0\n");
continue;
}
bfs(); if(ans == -1)
printf("-1\n");
else
printf("%d\n",ans);
}
return 0;
}