走迷宫 ~
不同的是题目给了你转向的方向序列
dis[x][y]表示到(x,y) 使用了最少的转向次数
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include <queue> using namespace std; const int maxn = 1010;
const int inf = (1<<30); int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1}; struct node
{
int x, y;
node(int i = 0, int j = 0)
{
x = i, y = j;
}
}; char s[1000010];
int g[maxn][maxn], dis[maxn][maxn], cost[1000010][4], dir[1000010]; int W,H,N;
queue<node>Q; void init()
{
memset(dis, -1, sizeof(dis));
memset(g, 0, sizeof(g)); dir[0] = 0;
for(int i = 1; i <= N; ++ i)
if(s[i] == 'L') dir[i] = (dir[i-1]+3)%4;
else dir[i] = (dir[i-1]+1)%4; for(int i = N; i >= 0; -- i)
for(int j = 0; j < 4; ++ j)
{
if(dir[i] == j) cost[i][j] = 0;
else
{
if(i == N) cost[i][j] = inf;
else cost[i][j] = cost[i+1][j] +1;
}
}
for(int i = 0; i < 4; ++ i) cost[N+1][i] = inf; while(!Q.empty()) Q.pop();
} bool solve(int sx, int sy, int ex, int ey)
{
Q.push(node(sx, sy));
dis[sx][sy] = 0;
while(!Q.empty())
{
node u = Q.front();
Q.pop();
int now = dis[u.x][u.y];
for(int i = 0; i < 4; ++ i)
{
int nx = u.x+dx[i], ny = u.y+dy[i];
if(g[nx][ny] && cost[now][i] < inf)
{
if(nx == ex && ny == ey) return true;
int tem = now+cost[now][i];
if(dis[nx][ny] == -1 || tem < dis[nx][ny])
{
dis[nx][ny] = tem;
Q.push(node(nx, ny));
}
}
}
}
return false;
} void show()
{
for(int i = 0; i <= W+1; ++ i)
{
for(int j = 0; j <= H+1; ++ j)
printf("%d ", g[i][j]);
puts("");
}
} int main()
{
while(scanf("%d%d%d", &W, &H, &N) ==3 && W+H+N)
{
scanf("%s", s+1);
init();
int sx, sy, ex, ey;
for(int i = 1; i <= W; ++ i)
{
scanf("%s", s+1);
for(int j = 1; j <= H; ++ j)
{
if(s[j] != '#') g[i][j] = 1;
if(s[j] == 'S') sx = i, sy = j;
if(s[j] == 'G') ex = i, ey = j;
}
}
// show();
if(solve(sx, sy, ex, ey)) puts("Yes");
else puts("No");
}
return 0;
}