oj.uz

Submission #972900

# Submission time Handle Problem Language Result Execution time Memory
972900 2024-05-01T10:01:36 Z vjudge1 Awesome Arrowland Adventure (eJOI19_adventure) C++17
0 / 100
 1 ms 1372 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int INF = 1e8;
const int N = 505;
vector<vector<int>>dist(N, vector<int>(N, INF));
char grid[N][N];
map<char, int>mp;

int dx(int c){
    if(c%4 == 0) return -1;
    if(c%4 == 2) return 1;
    return 0;
}

int dy(int c){
    if(c%4 == 1) return 1;
    if(c%4 == 3) return -1;
    return 0;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    mp['N'] = 0; mp['E'] = 1; mp['S'] = 2; mp['W'] = 3;
    int R, C; cin >> R >> C;

    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++)
            cin >> grid[i][j];
    }  

    dist[1][1] = 0;
    priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>>q; q.emplace(0, 1, 1);

    const auto ok = [&](int x, int y) -> bool {
        return (1 <= x && x <= R && 1 <= y && y <= C);
    };

    while(!q.empty()){
        auto [d, x, y] = q.top(); q.pop();
        if(grid[x][y] == 'X') continue;
        if(d > dist[x][y]) continue;

        for(int i = 0; i <= 3; i++){
            int nx = x + dx(mp[grid[x][y]] + i);
            int ny = y + dy(mp[grid[x][y]] + i);

            if(ok(nx, ny) && dist[nx][ny] > dist[x][y] + i){
                dist[nx][ny] = dist[x][y] + i;
                q.emplace(dist[nx][ny], nx, ny);
            }
        }
    }

    for(int i = 1; i <= R; i++){
        for(int j = 1; j <= C; j++) cout << dist[i][j] << " ";
        cout << endl;
    }

    if(dist[R][C] == INF) dist[R][C] = -1;
    cout << dist[R][C] << '\n';

    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1368 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1372 KB Output isn't correct
2 Halted 0 ms 0 KB -