UVa (BFS) The Monocycle

时间:2022-01-14 15:20:18

题目不光要求要到达终点而且要求所走的步数为5的倍数,每个时刻有三个选择,前进,左转弯,右转弯。

所以在vis数组中新增加两个维度即可,vis[x][y][dir][color]表示在(x, y)格子方向朝dir与地面接触的扇形的颜色为color,这个状态是否到达过。

 #include <cstdio>
#include <queue>
#include <cstring>
using namespace std; const int maxn = ;
char maze[maxn][maxn];
bool vis[maxn][maxn][][]; struct Node
{
int x, y, d, t, step;
Node(int x=, int y=, int d=, int t=, int step=):x(x), y(y), d(d), t(t), step(step) {}
}st, ed; int dx[] = { -, , , };
int dy[] = { , , , - }; int row, col; inline bool in(int x, int y)
{ return x >= && x < row && y >= && y < col; } int BFS()
{
memset(vis, false, sizeof(vis));
queue<Node> Q;
Q.push(st);
vis[st.x][st.y][][] = true;
while(!Q.empty())
{
Node now = Q.front(); Q.pop();
if(now.x == ed.x && now.y == ed.y && now.step % == )
return now.t; int d = now.d;
int x = now.x + dx[d];
int y = now.y + dy[d];
int t = now.t + ;
int step = now.step + ;
if(in(x, y) && maze[x][y] != '#' && !vis[x][y][d][step%])
{
Q.push(Node(x, y, d, t, step));
vis[x][y][d][step%] = true;
} for(int i = ; i <= ; i += )
{
x = now.x; y = now.y;
d = (now.d + i) % ;
t = now.t + ;
step = now.step;
if(!vis[x][y][d][step%])
{
Q.push(Node(x, y, d, t, step));
vis[x][y][d][step%] = true;
}
}
}
return -;
} int main()
{
//freopen("in.txt", "r", stdin); int kase = ;
while(scanf("%d%d", &row, &col) == )
{
if(row == && col == ) break; if(kase++ > ) puts("");
printf("Case #%d\n", kase); if(row == && col == ) break;
for(int i = ; i < row; i++) scanf("%s", maze[i]);
for(int i = ; i < row; i++)
for(int j = ; j < col; j++)
{
if(maze[i][j] == 'S') st = Node(i, j, , , );
if(maze[i][j] == 'T') ed = Node(i, j);
} int ans = BFS();
if(ans >= ) printf("minimum time = %d sec\n", ans);
else puts("destination not reachable");
} return ;
}

代码君