Submission #637369

#	Time	Username	Problem	Language	Result	Execution time	Memory
637369		VitaliyFS	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	12 / 100	1 ms	344 KiB

adventure

#include<bits/stdc++.h>

using namespace std;

#define fr first
#define sc second

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef long double ld;

const ll INF = 1000000000000000007, DIM = 507, DIM2 = 107, MAXN = 100007, MOD = 1000000007;

ll tt, mid, res,f, a[DIM], b[DIM], d[DIM][DIM], dist[DIM][DIM], used[DIM],  dp[DIM], y, type, ptr, root, cnt, sum, pos, h, p, sx,sy, id, testcase, curans, nn, split, n, m, x, k1, k2, changecnt,k,l,r,v,u, l1,r1,l2,r2;
bool flag, flag2;
char c;
string s[DIM];
priority_queue<pair<ll, pll>, vector<pair<ll, pll>>, greater<pair<ll, pll>>> q;

void check(ll x, ll y, ll x2, ll y2, char ch) {
	if(x2<1||x2>n||y2<1||y2>m)return;
	if(dist[x][y] + d[s[x][y]][ch] < dist[x2][y2]){
		dist[x2][y2]=dist[x][y] + d[s[x][y]][ch];
		q.push({dist[x2][y2], {x2,y2}});
	}
}

void solve() {
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		cin>>s[i];s[i]="&"+s[i];
	}
	d['N']['E']=1;
	d['N']['S']=2;
	d['N']['W']=3;
	d['E']['S']=1;
	d['E']['W']=2;
	d['E']['N']=3;
	d['S']['W']=1;
	d['S']['N']=2;
	d['S']['E']=3;
	d['W']['N']=1;
	d['W']['E']=2;
	d['W']['S']=3;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			dist[i][j] =INF;
	dist[1][1] = 0;
	q.push({0, {1,1}});
	while(!q.empty()){
		x=q.top().sc.fr; y = q.top().sc.sc;q.pop();
		if(s[x][y]=='X')continue;
		check(x,y,x+1,y,'S');
		check(x,y,x-1,y,'N');
		check(x,y,x,y+1,'W');
		check(x,y,x,y-1,'E');
	}
	if(dist[n][m]==INF){cout<<"-1\n";return;}
	cout<<dist[n][m]<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	tt=1;
	// freopen("input.txt","r",stdin);
	// freopen("output.txt","w",stdout);
	//cin>>tt;
	while(tt--) {
		solve();
	}
	return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'void check(ll, ll, ll, ll, char)':
adventure.cpp:23:27: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |  if(dist[x][y] + d[s[x][y]][ch] < dist[x2][y2]){
      |                           ^
adventure.cpp:23:29: warning: array subscript has type 'char' [-Wchar-subscripts]
   23 |  if(dist[x][y] + d[s[x][y]][ch] < dist[x2][y2]){
      |                             ^~
adventure.cpp:24:38: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |   dist[x2][y2]=dist[x][y] + d[s[x][y]][ch];
      |                                      ^
adventure.cpp:24:40: warning: array subscript has type 'char' [-Wchar-subscripts]
   24 |   dist[x2][y2]=dist[x][y] + d[s[x][y]][ch];
      |                                        ^~

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