Submission #244272

#	Time	Username	Problem	Language	Result	Execution time	Memory
244272		Matteo_Verz	Awesome Arrowland Adventure (eJOI19_adventure)	C++11	100 / 100	97 ms	21112 KiB

adventure

/*
                `-/oo+/-   ``
              .oyhhhhhhyo.`od
             +hhhhyyoooos. h/
            +hhyso++oosy- /s
           .yoooossyyo:``-y`
            ..----.` ``.-/+:.`
                   `````..-::/.
                  `..```.-::///`
                 `-.....--::::/:
                `.......--::////:
               `...`....---:::://:
             `......``..--:::::///:`
            `---.......--:::::////+/`
            ----------::::::/::///++:
            ----:---:::::///////////:`
            .----::::::////////////:-`
            `----::::::::::/::::::::-
             `.-----:::::::::::::::-
               ...----:::::::::/:-`
                 `.---::/+osss+:`
                   ``.:://///-.
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <cmath>

using namespace std;

const int INF = 2e9;
const int N = 500;

int n, m;

vector <pair <int, int>> g[5 + N * N];
bool viz[5 + N * N];
int dp[5 + N * N];

class Min_Heap {
    private:
        pair <int, int> h[5 + N * N];
        int sz;

        void Sift_Up(int pos) {
            int parent;
            parent = pos >> 1;

            while(h[pos].second < h[parent].second && parent > 0) {
                swap(h[pos], h[parent]);

                pos = parent;
                parent = pos >> 1;
            }
        }

        void Sift_Down(int pos) {
            int child;
            child = pos << 1;

            if(child + 1 <= sz && h[child].second > h[child + 1].second)
                child++;
            while(child <= sz && h[child].second < h[pos].second) {
                swap(h[pos], h[child]);

                pos = child;
                child = pos << 1;

                if(child + 1 <= sz && h[child].second > h[child + 1].second) child++;
            }
        }

    public:
        void Clear() {
            sz = 0;
        }

        void Push(pair <int, int> val) {
            h[++sz] = val;
            Sift_Up(sz);
        }

        void Pop() {
            swap(h[1], h[sz]);
            sz--;
            Sift_Down(1);
        }

        pair <int, int> Top() {
            return h[1];
        }

        int Size() {
            return sz;
        }
};
Min_Heap heap;

void Dijkstra(int nodStart) {
    for(int i = 1; i <= n * m; i++) dp[i] = INF;

    dp[nodStart] = 0;
    heap.Push(make_pair(nodStart, 0));

    while(heap.Size()) {
        pair <int, int> top = heap.Top();
        heap.Pop();

        if(viz[top.first] == false) {
            viz[top.first] = true;

            for(auto to : g[top.first]) {
                if(dp[to.first] > to.second + dp[top.first]) {
                    dp[to.first] = to.second + dp[top.first];
                    heap.Push(make_pair(to.first, dp[to.first]));
                }
            }
        }
    }
}

int main() {
#ifdef BLAT
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#endif // BLAT

    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        string s;
        cin >> s;

        for(int j = 0; j < s.size(); j++) {
            int idx = (i - 1) * m + j + 1;
            int idxn, idxe, idxs, idxw;
            idxn = idx - m;
            idxs = idx + m;
            idxe = idx + 1;
            idxw = idx - 1;

            if(s[j] == 'N') {
                if(i > 1) g[idx].push_back(make_pair(idxn, 0));
                if(j < m - 1) g[idx].push_back(make_pair(idxe, 1));
                if(i < n) g[idx].push_back(make_pair(idxs, 2));
                if(j > 0) g[idx].push_back(make_pair(idxw, 3));
            } else if(s[j] == 'E') {
                if(i > 1) g[idx].push_back(make_pair(idxn, 3));
                if(j < m - 1) g[idx].push_back(make_pair(idxe, 0));
                if(i < n) g[idx].push_back(make_pair(idxs, 1));
                if(j > 0) g[idx].push_back(make_pair(idxw, 2));
            } else if(s[j] == 'S') {
                if(i > 1) g[idx].push_back(make_pair(idxn, 2));
                if(j < m - 1) g[idx].push_back(make_pair(idxe, 3));
                if(i < n) g[idx].push_back(make_pair(idxs, 0));
                if(j > 0) g[idx].push_back(make_pair(idxw, 1));
            } else if(s[j] == 'W') {
                if(i > 1) g[idx].push_back(make_pair(idxn, 1));
                if(j < m - 1) g[idx].push_back(make_pair(idxe, 2));
                if(i < n) g[idx].push_back(make_pair(idxs, 3));
                if(j > 0) g[idx].push_back(make_pair(idxw, 0));
            }
        }
    }

    Dijkstra(1);

    if(dp[n * m] == INF) cout << -1 << '\n';
    else cout << dp[n * m] << '\n';
    return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:141:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int j = 0; j < s.size(); j++) {
                        ~~^~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 12 / 12
• Subtask 4: 16 / 16
• Subtask 5: 50 / 50