제출 #1197753

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1197753		mishasim	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	571 ms	4624 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]);
        }
    }
    if(dist[n][m]==INF)cout<<-1<<endl;
    else cout<<dist[n][m]<<endl;
    return 0;
}

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