oj.uz

Submission #276793

# Submission time Handle Problem Language Result Execution time Memory
276793 2020-08-20T16:44:50 Z JuliusMieliauskas Awesome Arrowland Adventure (eJOI19_adventure) C++14
34 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;

#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vll vector<long long>
#define MOD 1000000007
#define endl '\n'

typedef long long ll;

void print(vi v){
    cout<<"Contents of vector:\n";
    for(auto x : v) cout<<x<<" ";
    cout<<endl<<endl;
}

int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, -1, 0, 1};

vector<pair<int, int> > adj[509];

int m, n;
char ar[509][509];
int dists[509 * 509];

bool in(int i, int j){
    return (i >= 0) && (j >= 0) && (i<m) && (j<n);
}

void fillAdj(){
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            if(ar[i][j] == 'E'){
                for(int k = 0; k<4; k++){
                    int ci = i + dy[k], cj = j + dx[k];

                    if(in(ci, cj)){
                        if(k == 0) { /// Going W
                            adj[i*n + j].push_back({ci*n + cj, 2});
                        }
                        if(k == 1) { /// Going N
                            adj[i*n + j].push_back({ci*n + cj, 3});
                        }
                        if(k == 2) { /// Going E
                            adj[i*n + j].push_back({ci*n + cj, 0});
                        }
                        if(k == 3) { /// Going S
                            adj[i*n + j].push_back({ci*n + cj, 1});
                        }
                    }
                }
            }
            if(ar[i][j] == 'W'){
                for(int k = 0; k<4; k++){
                    int ci = i + dy[k], cj = j + dx[k];

                    if(in(ci, cj)){
                        if(k == 0) { /// Going W
                            adj[i*n + j].push_back({ci*n + cj, 0});
                        }
                        if(k == 1) { /// Going N
                            adj[i*n + j].push_back({ci*n + cj, 1});
                        }
                        if(k == 2) { /// Going E
                            adj[i*n + j].push_back({ci*n + cj, 2});
                        }
                        if(k == 3) { /// Going S
                            adj[i*n + j].push_back({ci*n + cj, 3});
                        }
                    }
                }
            }
            if(ar[i][j] == 'S'){
                for(int k = 0; k<4; k++){
                    int ci = i + dy[k], cj = j + dx[k];

                    if(in(ci, cj)){
                        if(k == 0) { /// Going W
                            adj[i*n + j].push_back({ci*n + cj, 1});
                        }
                        if(k == 1) { /// Going N
                            adj[i*n + j].push_back({ci*n + cj, 2});
                        }
                        if(k == 2) { /// Going E
                            adj[i*n + j].push_back({ci*n + cj, 3});
                        }
                        if(k == 3) { /// Going S
                            adj[i*n + j].push_back({ci*n + cj, 0});
                        }
                    }
                }
            }
            if(ar[i][j] == 'N'){
                for(int k = 0; k<4; k++){
                    int ci = i + dy[k], cj = j + dx[k];

                    if(in(ci, cj)){
                        if(k == 0) { /// Going W
                            adj[i*n + j].push_back({ci*n + cj, 3});
                        }
                        if(k == 1) { /// Going N
                            adj[i*n + j].push_back({ci*n + cj, 0});
                        }
                        if(k == 2) { /// Going E
                            adj[i*n + j].push_back({ci*n + cj, 1});
                        }
                        if(k == 3) { /// Going S
                            adj[i*n + j].push_back({ci*n + cj, 2});
                        }
                    }
                }
            }
        }
    }
}

void dijkstra(int source){
    bool visited[n*m];
    for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++) dists[i*n + j] = INT_MAX;
    }
    for(int i = 0; i<m; i++) for(int j = 0; j<n; j++) visited[i*n + j] = false;
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    pq.push({0, source});
    dists[source] = 0;
    while (!pq.empty()) {
        int u = pq.top().second; pq.pop();

        if (visited[u]) continue;
        else visited[u] = true;
        //cout<<"From "<<u<<":"<<endl;
        for(auto v : adj[u]) {
            //cout<<v.first<<endl;
            if (dists[v.first] > dists[u] + v.second) {
                dists[v.first] = dists[u] + v.second;
                pq.push({dists[v.first], v.first});
            }
        }
        //cout<<endl;
    }
}

void solve(){
    cin>>m>>n;
    for(int i = 0; i<m; i++) for(int j = 0; j<n; j++) cin>>ar[i][j];
    fillAdj();
    dijkstra(0);

    /*for(int i = 0; i<m; i++){
        for(int j = 0; j<n; j++){
            cout<<dists[i*n + j]<<" ";
        }
        cout<<endl;
    }*/

    if(dists[m*n - 1] == INT_MAX) cout<<"-1"<<endl;
    else cout<<dists[m*n - 1]<<endl;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    //ifstream cin(""); ofstream cout("");///cia failai

    //int T; cin>>T;
    int T = 1;

    for(int it = 1; it<=T; it++){
        solve();

    }
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Runtime error 1 ms 512 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -