Submission #1197748

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197748		mishasim	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	0 / 100	0 ms	328 KiB

adventure

#include <bits/stdc++.h>

using namespace std;

long long dist[507][507],k[507][507];
string s;
long long n,m,x,y;
queue<pair<int,int>> q;
const long INF = 100000000000;
pair<int,int> v;

void check(int x, int y, int val){
    if(x>n || y>m || x<1 || y<1)return;
    if(dist[x][y]>val){
        dist[x][y] = val;
        q.push({x,y});
    }
}

int main()
{
    cin>>n>>m;
    for(int i = 1 ; i<=n ; i++){
        cin>>s;
        for(int j = 1 ; j<=m ; j++){
            if(s[j-1]=='N')k[i][j] = 1;
            if(s[j-1]=='E')k[i][j] = 2;
            if(s[j-1]=='S')k[i][j] = 3;
            if(s[j-1]=='W')k[i][j] = 4;
        }
    }
    for(int i = 1 ; i<=n ; i++){
        for(int j = 1 ; j<=m ; j++){
            dist[i][j] = INF;
        }
    }
    dist[1][1] = 0;
    q.push({1,1});
    while(!q.empty()){
        v = q.front();
        q.pop();
        x = v.first;y = v.second;
        if(k[x][y]==1){
            check(x-1,y,dist[x][y]);
            check(x+1,y,dist[x][y]+2);
            check(x,y+1,dist[x][y]+1);
            check(x,y-1,dist[x][y]+3);
        }
        if(k[x][y]==2){
            check(x-1,y,dist[x][y]+3);
            check(x+1,y,dist[x][y]+1);
            check(x,y+1,dist[x][y]);
            check(x,y-1,dist[x][y]+2);
        }
        if(k[x][y]==3){
            check(x-1,y,dist[x][y]+2);
            check(x+1,y,dist[x][y]);
            check(x,y+1,dist[x][y]+3);
            check(x,y-1,dist[x][y]+1);
        }
        if(k[x][y]==4){
            check(x-1,y,dist[x][y]+1);
            check(x+1,y,dist[x][y]+3);
            check(x,y+1,dist[x][y]+2);
            check(x,y-1,dist[x][y]);
        }
    }
    cout<<dist[n][m];
    return 0;
}

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