314 - Robot(用Dijkstra怎么还ac不了)

#include <cstdio>
#include <cstring>
#include <queue>
#include <string>

using namespace std;

const int N = 55;
const int M = 4;
const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};
const int INF = 0x3f3f3f3f;

struct HeapNode
{
    int x, y, d, dir;
    bool operator < (const HeapNode &other) const
    {
        return d > other.d;
    }
};

int n, m;
bool vis[M][N][N];
int grid[N][N];
int curdir;
int srcx, srcy, dstx, dsty;
char buf[N];
int d[M][N][N];

int main()
{
#ifndef ONLINE_JUDGE
    freopen("e:\uva_in.txt", "r", stdin);
#endif

    while (scanf("%d%d", &m, &n) == 2 && (n || m)) {
        memset(grid, 0x00, sizeof(grid));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &grid[i][j]);
            }
        }

        for (int i = m - 1; i >= 0; i--) {
            for (int j = n - 1; j >= 0; j--) {
                if (grid[i][j]) {
                    grid[i + 1][j] = grid[i][j + 1] = grid[i + 1][j + 1] = 1;
                }
            }
        }
        scanf("%d%d%d%d%s", &srcx, &srcy, &dstx, &dsty, buf);
        string s = buf;
        if (s == "north") curdir = 0;
        else if (s == "east") curdir = 1;
        else if (s == "south") curdir = 2;
        else curdir = 3;

        //printf("srcx=%d, srcy=%d, dstx=%d, dsty=%d, curdir=%dn", srcx, srcy, dstx, dsty, curdir);

        if (grid[srcx][srcy] || grid[dstx][dsty]) {
            printf("-1n");
            continue;
        }

        if (srcx < 0 || srcx >= m || srcy < 0 || srcy >= n) {
            printf("-1n");
            continue;
        }

        if (dstx < 0 || dstx >= m || dsty < 0 || dsty >= n) {
            printf("-1n");
            continue;
        }

        priority_queue<HeapNode> q;
        HeapNode node;
        bool found = false;
        node.x = srcx, node.y = srcy, node.d = 0, node.dir = curdir;
        q.push(node);
        memset(d, 0x3f, sizeof(d));
        d[curdir][srcx][srcy] = 0;
        memset(vis, false, sizeof(vis));

        while (!q.empty()) {
            HeapNode tmp = q.top(); q.pop();
            int curx = tmp.x, cury = tmp.y;
            int curdir = tmp.dir;

            //printf("curx=%d, cury=%d, curdir=%d, d=%dn", curx, cury, curdir, tmp.d);

            if (curx == dstx && cury == dsty) {
                found = true;
                printf("%dn", tmp.d);
                break;
            }

            if (vis[curdir][curx][cury]) continue;
            vis[curdir][curx][cury] = true;

            int newDir = (curdir + 1) % 4;
            int x = curx, y = cury;
            if (d[curdir][curx][cury] + 1 < d[newDir][curx][cury]) {
                d[newDir][curx][cury] = d[curdir][curx][cury] + 1;
                node.x = x, node.y = y, node.dir = newDir, node.d = d[newDir][curx][cury];
                q.push(node);
            }

            newDir = (curdir + 3) % 4;
            x = curx, y = cury;
            if (d[curdir][curx][cury] + 1 < d[newDir][curx][cury]) {
                d[newDir][curx][cury] = d[curdir][curx][cury] + 1;
                node.x = x, node.y = y, node.dir = newDir, node.d = d[newDir][curx][cury];
                q.push(node);
            }

            newDir = curdir;
            for (int i = 1; i <= 3; i++) {
                x = curx + dx[curdir] * i;
                y = cury + dy[curdir] * i;
                if (x < 0 || x >= m || y < 0 || y >= n) break;
                if (grid[x][y]) break;

                if (d[curdir][curx][cury] + 1 < d[newDir][x][y]) {
                    d[newDir][x][y] = d[curdir][curx][cury] + 1;
                    node.x = x, node.y = y, node.dir = newDir, node.d = d[newDir][x][y];
                    q.push(node);
                }
            }


        }

        if (!found) {
            printf("-1n");
        }
    }

    return 0;
}

最后

以上就是年轻香氛为你收集整理的314 - Robot(用Dijkstra怎么还ac不了)的全部内容，希望文章能够帮你解决314 - Robot(用Dijkstra怎么还ac不了)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。