Submission #244269

#	Time	Username	Problem	Language	Result	Execution time	Memory
244269		Matteo_Verz	Awesome Arrowland Adventure (eJOI19_adventure)	C++11	100 / 100	124 ms	21492 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];

priority_queue <pair <int, int>, vector <pair <int, int>>, greater <pair <int, int>>> heap;

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

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

    while(heap.size()) {
        pair <int, int> top = heap.top();
        heap.pop();

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

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

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

    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:85: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