Submission #1250045

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250045		Petrix	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	176 ms	14756 KiB

adventure

#include <iostream>
#include <queue>
using namespace std;

int dir[501][501],n,m;
int dist[501][501];
int ml[]={0,1,0,-1};
int mc[]={-1,0,1,0};

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

bool in(int l,int c){
    return (l>=0 && c>=0 && l<n && c<m);
}

int main()
{
    int i,j,l,c,cost;
    char ch;
	cin>>n>>m;
	for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            cin>>ch;
            if(ch=='X') dir[i][j]=-1;
            else if(ch=='N') dir[i][j]=0;
            else if(ch=='E') dir[i][j]=1;
            else if(ch=='S') dir[i][j]=2;
            else if(ch=='W') dir[i][j]=3;
        }
	}
	for(i=0;i<n;i++) for(j=0;j<m;j++) dist[i][j]=-1;
	q.push({0,{0,0}});
	while(!q.empty()){
        auto it=q.top();q.pop();
		l=it.second.first;
        c=it.second.second;
        cost=it.first;
		if(!in(c,l) || dist[c][l]!=-1) continue;
		dist[c][l]=cost;
		if(dir[c][l]==-1) continue;
		for(i=0;i<4;i++){
            q.push({cost+i,{l+ml[(dir[c][l]+i)%4],c+mc[(dir[c][l]+i)%4]}});
		}
	}
	cout<<dist[n-1][m-1];
	return 0;
}

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