oj.uz

Submission #276384

# Submission time Handle Problem Language Result Execution time Memory
276384 2020-08-20T12:31:31 Z JuliusMieliauskas Awesome Arrowland Adventure (eJOI19_adventure) C++14
34 / 100
 1 ms 388 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};

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 bfs(int i, int j){
    queue< pair<int, int> > q;
    for(int i = 0; i<m; i++) for(int j = 0; j<n; j++) dists[i][j] = INT_MAX;
    dists[i][j] = 0;
    q.push({i, j});
    while(!q.empty()){
        pair<int, int> p = q.front(); q.pop();
        int ci = p.first, cj = p.second;
        //cout<<"Ci: "<<ci<<"  cj: "<<cj<<"   ar at ci, cj: "<<ar[ci][cj]<<endl;

        if(ar[ci][cj] == 'E'){
            //cout<<"Looking E"<<endl;
            for(int i = 0; i<4; i++){
                if(in(ci + dy[i], cj + dx[i])){
                    //cout<<"Inside with "<<ci+dy[i]<<", "<<cj+dx[i]<<endl;
                    if(i == 0) { /// Going W
                        if(dists[ci][j] + 2 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 2;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 1) { /// Going N
                        if(dists[ci][cj] + 3 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 3;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 2) { /// Going E
                        if(dists[ci][cj] < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj];
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 3) { /// Going S
                        if(dists[ci][cj] + 1 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 1;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }

                }
            }
        }

        if(ar[ci][cj] == 'S'){
        //cout<<"Looking S"<<endl;
            for(int i = 0; i<4; i++){
                if(in(ci + dy[i], cj + dx[i])){
                    if(i == 0) { /// Going W
                        if(dists[ci][cj] + 1 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 1;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 1) { /// Going N
                        if(dists[ci][cj] + 2 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 2;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 2) { /// Going E
                        if(dists[ci][cj] + 3< dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 3;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 3) { /// Going S
                        if(dists[ci][cj]< dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj];
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }

                }
            }
        }

        if(ar[ci][cj] == 'W'){
        //cout<<"Looking W"<<endl;
            for(int i = 0; i<4; i++){
                if(in(ci + dy[i], cj + dx[i])){
                    if(i == 0) { /// Going W
                        if(dists[ci][cj] < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj];
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 1) { /// Going N
                        if(dists[ci][cj] + 1 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 1;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 2) { /// Going E
                        if(dists[ci][cj] + 2< dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 2;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 3) { /// Going S
                        if(dists[ci][cj] + 3 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 3;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }

                }
            }
        }

        if(ar[ci][cj] == 'N'){
        //cout<<"Looking N"<<endl;
            for(int i = 0; i<4; i++){
                if(in(ci + dy[i], cj + dx[i])){
                    if(i == 0) { /// Going W
                        if(dists[ci][cj] + 3 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 3;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 1) { /// Going N
                        if(dists[ci][cj] < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj];
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 2) { /// Going E
                        if(dists[ci][cj] + 1 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 1;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }
                    if(i == 3) { /// Going S
                        if(dists[ci][cj] + 2 < dists[ci + dy[i]][cj + dx[i]]){
                            dists[ci + dy[i]][cj + dx[i]] = dists[ci][cj] + 2;
                            q.push({ci + dy[i], cj + dx[i]});
                        }
                    }

                }
            }
        }
    }
}

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

    if(m == 1){
        ll ans = 0;
        for(int i = 0; i<n-1; i++){
            if(ar[0][i] == 'N') ans++;
            if(ar[0][i] == 'S') ans += 3;
            if(ar[0][i] == 'W') ans += 2;
            if(ar[0][i] == 'X'){
                ans = -1;
                break;
            }
        }
        cout<<ans<<endl;
        return;
    }

    bfs(0, 0);

    if(dists[m-1][n-1] == INT_MAX) cout<<"-1"<<endl;
    else cout<<dists[m-1][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 0 ms 384 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 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 0 ms 384 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 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 0 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 288 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 Correct 1 ms 384 KB Output is correct
2 Incorrect 1 ms 384 KB Output isn't correct
3 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 0 ms 384 KB Output is correct
3 Correct 1 ms 388 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 0 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 0 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 288 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Incorrect 1 ms 384 KB Output isn't correct
27 Halted 0 ms 0 KB -