Submission #1119315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1119315		Dan4Life	Awesome Arrowland Adventure (eJOI19_adventure)	C++17	100 / 100	32 ms	10324 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
using ar4 = array<int,4>;
const int N = (int)5e2+10;
string s[N];
int X[] = {-1,0,1,0};
int Y[] = {0,1,0,-1};
int n, m, dis[N][N][5];

void bfs01(){
	deque<ar4> dq;
	memset(dis,0x3f,sizeof(dis));
	dq.pb({0,0,0,s[0][0]}); dis[0][0][s[0][0]]=0;
	while(sz(dq)){
		auto [D,i,j,d] = dq[0]; dq.pop_front();
		if(d==4) continue; 
		int x = i+X[d], y = j+Y[d]; d++; d%=4;
		if(x>=0 and y>=0 and x<n and y<m and dis[x][y][s[x][y]]>D)
			dis[x][y][s[x][y]]=D, dq.push_front({D,x,y,s[x][y]});
		if(dis[i][j][d]-1>D) dis[i][j][d]=D+1,dq.push_back({D+1,i,j,d});
	}
	int ans = N*N*N;
	for(int i : {0,1,2,3,4}) 
		ans=min(ans,dis[n-1][m-1][i]);
	if(ans==N*N*N) ans=-1; cout << ans;
}

int32_t main(){
	cin >> n >> m;
	for(int i = 0; i < n; i++){
		cin >> s[i];
		for(int j = 0; j < m; j++){
			char c = s[i][j];
			if(c=='N') c = 0;
			else if(c=='E') c = 1;
			else if(c=='S') c = 2;
			else if(c=='W') c = 3;
			else c = 4;
			s[i][j] = c;
		}
	}
	bfs01();
}

Compilation message (stderr)

adventure.cpp: In function 'void bfs01()':
adventure.cpp:15:43: warning: array subscript has type 'char' [-Wchar-subscripts]
   15 |  dq.pb({0,0,0,s[0][0]}); dis[0][0][s[0][0]]=0;
      |                                           ^
adventure.cpp:20:57: warning: array subscript has type 'char' [-Wchar-subscripts]
   20 |   if(x>=0 and y>=0 and x<n and y<m and dis[x][y][s[x][y]]>D)
      |                                                         ^
adventure.cpp:21:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   21 |    dis[x][y][s[x][y]]=D, dq.push_front({D,x,y,s[x][y]});
      |                     ^
adventure.cpp:27:2: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   27 |  if(ans==N*N*N) ans=-1; cout << ans;
      |  ^~
adventure.cpp:27:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   27 |  if(ans==N*N*N) ans=-1; cout << ans;
      |                         ^~~~

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