Submission #1262687

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262687		iordache_	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	98 ms	44212 KiB

adventure

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int N=5e2+5;
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
char v[N][N];
int dir[N][N];
struct Point
{
    int x,y;
};
bool cmp(pair<int,Point> a, pair<int,Point> b)
{
    return a.first>b.first;
}
vector<pair<Point,int>> g[N][N];
int dist[N][N];
signed main()
{
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int n,m;
    cin>>n>>m;
    char ch;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) cin>>v[i][j];
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
    {
        if(v[i][j]=='X') continue;
        if(v[i][j]=='N') dir[i][j]=0;
        if(v[i][j]=='E') dir[i][j]=1;
        if(v[i][j]=='S') dir[i][j]=2;
        if(v[i][j]=='W') dir[i][j]=3;
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
    {
        if(v[i][j]=='X') continue;
        for(int d=0;d<4;++d)
        {
            int ni=i+dx[d],nj=j+dy[d];
            if(ni<1||ni>n||nj<1||nj>m) continue;
            g[i][j].pb({{ni,nj},(d-dir[i][j]+4)%4});
        }
    }
    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>> pq;
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) dist[i][j]=1e18;
    dist[1][1]=0;
    pq.push({0,{1,1}});
    while(!pq.empty())
    {
        int x=pq.top().second.first,y=pq.top().second.second;
        pq.pop();
        for(auto p:g[x][y])
        {
            int nx=p.first.x,ny=p.first.y;
            if(dist[nx][ny]<=dist[x][y]+p.second) continue;
            dist[nx][ny]=dist[x][y]+p.second;
            pq.push({dist[nx][ny],{nx,ny}});
        }
    }
    cout<<(dist[n][m]==1e18 ? -1:dist[n][m]);
}

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