Submission #976185

#	Time	Username	Problem	Language	Result	Execution time	Memory
976185		vjudge1	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	47 ms	4848 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int N = 5e2 + 5;

char grid[N][N];

int n, m;

vector < vector < bool > > vis ( N, vector < bool > ( N, 0));

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

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    cin >> n >> m;

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

    pq.push({0, {1, 1}});

    while ( !pq.empty()){
        int x = pq.top().second.first, y = pq.top().second.second, val = pq.top().first;
        pq.pop();

        if ( x == n && y == m ){
            cout << val << endl;
            return 0;
        }

        if ( vis[x][y] ) continue; vis[x][y] = 1;

        if ( grid[x][y] == 'N'){
            if ( x - 1 >= 1 && !vis[x-1][y] && (( grid[x - 1][y] != 'X' && !( x - 1 == n && y == m )) || ( x - 1 == n && y == m )) ) pq.push({val, {x - 1, y}});
            if ( y + 1 <= m && !vis[x][y + 1] && (( grid[x][y+1] != 'X' && !( x == n && y + 1 == m )) || ( x == n && y + 1 == m)) ) pq.push({val + 1, {x, y + 1}});
            if ( x + 1 <= n && !vis[x + 1][y] && (( grid[x + 1][y] != 'X' && !( x + 1 == n && y == m )) || ( x + 1 == n && y == m)) ) pq.push({val + 2, {x + 1, y}});
            if ( y - 1 >= 1 && !vis[x][y - 1] && (( grid[x][y - 1] != 'X' && !( x == n && y - 1 == m )) || ( x == n && y - 1 == m )) ) pq.push({val + 3, {x, y - 1}});
        }

        else if ( grid[x][y] == 'E'){
            if ( x - 1 >= 1 && !vis[x-1][y] && (( grid[x - 1][y] != 'X' && !( x - 1 == n && y == m )) || ( x - 1 == n && y == m )) ) pq.push({val + 3, {x - 1, y}});
            if ( y + 1 <= m && !vis[x][y + 1]&& (( grid[x][y+1] != 'X' && !( x == n && y + 1 == m )) || ( x == n && y + 1 == m))) pq.push({val, {x, y + 1}});
            if ( x + 1 <= n && !vis[x + 1][y]&& (( grid[x + 1][y] != 'X' && !( x + 1 == n && y == m )) || ( x + 1 == n && y == m))) pq.push({val + 1, {x + 1, y}});
            if ( y - 1 >= 1 && !vis[x][y - 1] && (( grid[x][y - 1] != 'X' && !( x == n && y - 1 == m )) || ( x == n && y - 1 == m ))) pq.push({val + 2, {x, y - 1}});
        }
        else if ( grid[x][y] == 'S'){
            if ( x - 1 >= 1 && !vis[x-1][y]&& (( grid[x - 1][y] != 'X' && !( x - 1 == n && y == m )) || ( x - 1 == n && y == m ))) pq.push({val + 2, {x - 1, y}});
            if ( y + 1 <= m && !vis[x][y + 1]&& (( grid[x][y+1] != 'X' && !( x == n && y + 1 == m )) || ( x == n && y + 1 == m))) pq.push({val + 3, {x, y + 1}});
            if ( x + 1 <= n && !vis[x + 1][y]&& (( grid[x + 1][y] != 'X' && !( x + 1 == n && y == m )) || ( x + 1 == n && y == m))) pq.push({val, {x + 1, y}});
            if ( y - 1 >= 1 && !vis[x][y - 1]&& (( grid[x][y - 1] != 'X' && !( x == n && y - 1 == m )) || ( x == n && y - 1 == m )) ) pq.push({val + 1, {x, y - 1}});
        }
        else if ( grid[x][y] == 'W'){
            if ( x - 1 >= 1 && !vis[x-1][y]&& (( grid[x - 1][y] != 'X' && !( x - 1 == n && y == m )) || ( x - 1 == n && y == m ))) pq.push({val + 1, {x - 1, y}});
            if ( y + 1 <= m && !vis[x][y + 1]&& (( grid[x][y+1] != 'X' && !( x == n && y + 1 == m )) || ( x == n && y + 1 == m))) pq.push({val + 2, {x, y + 1}});
            if ( x + 1 <= n && !vis[x + 1][y]&& (( grid[x + 1][y] != 'X' && !( x + 1 == n && y == m )) || ( x + 1 == n && y == m))) pq.push({val + 3, {x + 1, y}});
            if ( y - 1 >= 1 && !vis[x][y - 1]&& (( grid[x][y - 1] != 'X' && !( x == n && y - 1 == m )) || ( x == n && y - 1 == m ))) pq.push({val, {x, y - 1}});
        }
    }

    cout << -1 << endl;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:37:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   37 |         if ( vis[x][y] ) continue; vis[x][y] = 1;
      |         ^~
adventure.cpp:37:36: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   37 |         if ( vis[x][y] ) continue; vis[x][y] = 1;
      |                                    ^~~

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