Submission #882581

#	Time	Username	Problem	Language	Result	Execution time	Memory
882581		db_123	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	38 / 100	1 ms	604 KiB

adventure

#include <iostream>
#include <vector>
#include <set>

using namespace std;

struct Info {
    int node;
    int cost;
    Info() = default;
    Info(int node, int cost) {
        this->node = node;
        this->cost = cost;
    }
    bool operator<(Info a2) const {
        if(cost == a2.cost) {
            return node<a2.node;
        }
        return cost<a2.cost;
    }
};

int n,m;
vector<vector<char>> ma;
vector<vector<Info>> graph;

void read() {
    cin>>n>>m;
    ma.resize(n+1, vector<char>(m+1));
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            cin>>ma[i][j];
        }
    }
}

void form_graph() {
    graph.resize(n*m+1);
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=m;j++) {
            vector<int> delta;
            if(ma[i][j] == 'N') {
                delta = {0, 1, 2, 3};
            }
            else if(ma[i][j] == 'E') {
                delta = {3, 0, 1, 2};
            }
            else if(ma[i][j] == 'S') {
                delta = {2, 3, 0, 1};
            }
            else {
                delta = {1, 2, 3, 0};
            }
            int curr_node = (i-1)*m + j;
            int node_dr = (i-1)*m + j + 1;
            int node_st = (i-1)*m + j - 1;
            int node_jos = i * m + j;
            int node_sus = (i-2)*m + j;
            if(i-1>0 && ma[i-1][j]!='X') {
                graph[curr_node].push_back(*new Info(node_sus, delta[0]));
            }
            if(j+1<=m && ((i==n && j==m-1) || ma[i][j+1]!='X')) {
                graph[curr_node].push_back(*new Info(node_dr, delta[1]));
            }
            if(i+1<=n && ((i==n-1 && j==m) || ma[i+1][j+1]!='X')) {
                graph[curr_node].push_back(*new Info(node_jos, delta[2]));
            }
            if(j-1>0 && ma[i][j-1]!='X') {
                graph[curr_node].push_back(*new Info(node_st, delta[3]));
            }
        }
    }
}

int dijkstra() {
    vector<int> dist(n*m+1, 1e9);
    set<Info> st;
    st.insert(*new Info(1, 0));
    dist[1] = 0;
    Info tp;
    while(!st.empty()) {
        tp = (*st.begin());
        st.erase(st.begin());
        for(auto it : graph[tp.node]) {
            if(dist[it.node] > dist[tp.node] + it.cost) {
                dist[it.node] = dist[tp.node] + it.cost;
                st.insert(*new Info(it.node, dist[it.node]));
            }
        }
    }
    if(dist[n*m]==1e9) {
        dist[n*m]=-1;
    }
    return dist[n*m];
}

void solve() {
    form_graph();
    cout<<dijkstra();
}

int main() {

    read();
    solve();
    return 0;
}

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