Submission #1026522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026522		LM1	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	132 ms	5216 KiB

adventure

#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
//#define int long long
#define pb push_back
#define ff first
#define ss second
using namespace std;
const int N=555;
char a[N][N];
int n,m,d[N][N];
int xx[4]={1,0,-1,0};
int yy[4]={0,1,0,-1};
//c1 aris
//c2 gvinda
int rot(int x2,int y2,int m1,int m2){
	char c1=a[x2][y2];
	char c2;
	if(m1==1)c2='S';
	if(m2==1)c2='E';
	if(m1==-1)c2='N';
	if(m2==-1)c2='W';
	if(c1==c2)return 0;
	string c3="";c3+=c1;c3+=c2;
	//cout<<c3<<" ";
	if(c3=="NE" or c3=="ES" or c3=="SW" or c3=="WN")return 1;
	if(c3=="NS" or c3=="EW" or c3=="SN" or c3=="WE")return 2;
	if(c3=="NW" or c3=="EN" or c3=="SE" or c3=="WS")return 3;
}
void dijkstra(){
	d[0][0]=0;
	priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>>pq;
	pq.push({0,{0,0}});
	while(pq.size()){
		auto st=pq.top();
		pq.pop();
		int x=st.ss.ff;
		int y=st.ss.ss;
		int d1=st.ff;
		if(a[x][y]=='X')continue;
		for(int i=0;i<4;i++){
			int xn=x+xx[i];
			int yn=y+yy[i];
			if(xn<0 or xn>n-1)continue;
			if(yn<0 or yn>m-1)continue;
			int r=rot(x,y,xx[i],yy[i]);
			if(d1+r<d[xn][yn]){
				d[xn][yn]=d1+r;
				pq.push({d[xn][yn],{xn,yn}});
			}
		}
	}
}
int main(){
	ios_base::sync_with_stdio(NULL);cin.tie(NULL);
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			d[i][j]=1e9;
			cin>>a[i][j];
		}
	}
	//cout<<rot(0,0,0,1);
	dijkstra();
//	for(int i=0;i<n;i++){
//		for(int j=0;j<m;j++){
//			cout<<d[i][j]<<" ";
//		}cout<<endl;
//	}
	if(d[n-1][m-1]==1e9)cout<<-1;
	else cout<<d[n-1][m-1];
}

Compilation message (stderr)

adventure.cpp: In function 'int rot(int, int, int, int)':
adventure.cpp:24:12: warning: control reaches end of non-void function [-Wreturn-type]
   24 |  string c3="";c3+=c1;c3+=c2;
      |            ^~

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