Submission #842093

#	Time	Username	Problem	Language	Result	Execution time	Memory
842093		Nika533	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	75 ms	34188 KiB

adventure

#pragma gcc diagnostic "-std=c++1z"
#pragma gcc optimize("Ofast");
#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define f first
#define s second
#define MOD 1000000007
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define allr(x) (x).rbegin(),(x).rend()
using namespace std;
const int N=505;
char arr[N][N];
int n,m,T,k,dist[N*N],fix[N*N];
vector<pii> g[N*N];
int val(int a, int b) {
     return (a-1)*m+b;
}
main () {
	ios :: sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
     cin>>n>>m;
     for (int i=1; i<=n; i++) {
          string s; cin>>s;
          for (int j=1; j<=m; j++) {
               dist[val(i,j)]=1e18;
               if (s[j-1]=='S') {
                    if (i<n) g[val(i,j)].pb({val(i+1,j),0});
                    if (j<m) g[val(i,j)].pb({val(i,j+1),3});
                    if (i>1) g[val(i,j)].pb({val(i-1,j),2});
                    if (j>1) g[val(i,j)].pb({val(i,j-1),1});
               }
               if (s[j-1]=='E') {
                    if (i<n) g[val(i,j)].pb({val(i+1,j),1});
                    if (j<m) g[val(i,j)].pb({val(i,j+1),0});
                    if (i>1) g[val(i,j)].pb({val(i-1,j),3});
                    if (j>1) g[val(i,j)].pb({val(i,j-1),2});
               }
               if (s[j-1]=='W') {
                    if (i<n) g[val(i,j)].pb({val(i+1,j),3});
                    if (j<m) g[val(i,j)].pb({val(i,j+1),2});
                    if (i>1) g[val(i,j)].pb({val(i-1,j),1});
                    if (j>1) g[val(i,j)].pb({val(i,j-1),0});
               }
               if (s[j-1]=='N') {
                    if (i<n) g[val(i,j)].pb({val(i+1,j),2});
                    if (j<m) g[val(i,j)].pb({val(i,j+1),1});
                    if (i>1) g[val(i,j)].pb({val(i-1,j),0});
                    if (j>1) g[val(i,j)].pb({val(i,j-1),3});
               }
          }
     }
     dist[1]=0; 
     priority_queue<pii> q; q.push({0,1});
     while (!q.empty()) {
		int v=q.top().s; q.pop();
		if (fix[v]) continue;
		fix[v]=1;
		for (auto x:g[v]) {
			int u=x.f,w=x.s; 
			if (dist[u]>dist[v]+w) {
				dist[u]=dist[v]+w;
				q.push({-dist[u],u});
			}
		}
     }
     // for (int i=1; i<=n; i++) {
     //      for (int j=1; j<=m; j++) {
     //           cout<<i<<" "<<j<<" "<<val(i,j)<<" "<<dist[val(i,j)]<<endl;
     //      }
     // }
     if (dist[n*m]==(int)1e18) cout<<-1<<endl;
     else cout<<dist[n*m]<<endl;
}

Compilation message (stderr)

adventure.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
adventure.cpp:2: warning: ignoring '#pragma gcc optimize' [-Wunknown-pragmas]
    2 | #pragma gcc optimize("Ofast");
      | 
adventure.cpp:20:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   20 | main () {
      | ^~~~

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