Submission #1243962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1243962		snowysmo	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	50 / 100	2092 ms	1352 KiB

adventure

#include<bits/stdc++.h>
#define ll long long
#define endl '\n'

using namespace std;

const int mx = 507, inf=1e7;
int n, m;
char c[mx][mx];
int ans[mx][mx];
int dx[]={1, -1, 0, 0}, dy[]={0, 0, 1, -1};
char cc[]={'N', 'S', 'W', 'E'};
map<pair<char, char>, int> mp;
bool isInside(int i, int j){
    return (i>=1 && i<=n && j>=1 && j<=m ? 1 : 0);
}
void go(int i, int j, char target, int temp){
    if(!isInside(i, j)) return;
    int x;
    if(c[i][j]!='X') x=temp+mp[{c[i][j], target}];
    else x=temp;
    if(ans[i][j]<=x) return;
    ans[i][j]=x;
    for(int k=0;k<4;k++) if(c[i+dx[k]][j+dy[k]]!='X') go(i+dx[k], j+dy[k], cc[k], ans[i][j]);
}
int main(){
    cin>>n>>m;
    mp[{'N','N'}]=0, mp[{'N','E'}]=1, mp[{'N','S'}]=2, mp[{'N','W'}]=3;
    mp[{'E','N'}]=3, mp[{'E','E'}]=0, mp[{'E','S'}]=1, mp[{'E','W'}]=2;
    mp[{'S','N'}]=2, mp[{'S','E'}]=3, mp[{'S','S'}]=0, mp[{'S','W'}]=1;
    mp[{'W','N'}]=1, mp[{'W','E'}]=2, mp[{'W','S'}]=3, mp[{'W','W'}]=0;
    for(int i=0;i<=n;i++) for(int j=0;j<=m;j++) ans[i][j]=inf;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>c[i][j];
    go(n, m, 'X', 0);
    if(ans[1][1]==inf) cout<<-1<<endl;
    else cout<<ans[1][1]<<endl;

    return 0;
}

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