Aizu 2325 Mysterious Maze

走迷宫 ~
不同的是题目给了你转向的方向序列
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;

}
巴特西

Aizu 2325 Mysterious Maze

最新文章

热门文章
