Submission #1364638

#	Time	Username	Problem	Language	Result	Execution time	Memory
1364638		kmath628	Awesome Arrowland Adventure (eJOI19_adventure)	C++20	100 / 100	9 ms	4460 KiB

adventure

#include <bits/stdc++.h>
using namespace std;
char s[509];
int dr[4]={-1,0,1,0},dc[4]={0,1,0,-1};
int a[509][509],d[509][509];
queue<pair<int,int> > q[4];
int main(){
    int m,n,i,j,k;
    scanf("%d %d",&m,&n);
    for(i=0;i<m;i++){
        scanf(" %s",s);
        for(j=0;j<n;j++){
            if(s[j]=='N') a[i][j]=0;
            else if(s[j]=='E') a[i][j]=1;
            else if(s[j]=='S') a[i][j]=2;
            else if(s[j]=='W') a[i][j]=3;
            else a[i][j]=-1;
        }
    }
    memset(d,127,sizeof(d));
    d[0][0]=0;
    q[0].push({0,0});
    while(1){
        bool flag=0;
        for(i=0;i<4;i++){
            while(!q[i].empty()){
                flag=1;
                auto [r,c]=q[i].front();
                q[i].pop();
                if(d[r][c]%4 != i || a[r][c]==-1) continue;
                for(k=0;k<4;k++){
                    int tr=r+dr[k],tc=c+dc[k],td=d[r][c]+(k-a[r][c]+4)%4;
                    if(tr>=0 && tr<m && tc>=0 && tc<n && d[tr][tc]>td){
                        d[tr][tc]=td;
                        q[td%4].push(make_pair(tr,tc));
                    }
                }
            }
        }
        if(!flag) break;
    }
    if(d[m-1][n-1] >= 4*m*n) printf("-1\n");
    else printf("%d\n",d[m-1][n-1]);
    return 0;
}

Compilation message (stderr)

adventure.cpp: In function 'int main()':
adventure.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d %d",&m,&n);
      |     ~~~~~^~~~~~~~~~~~~~~
adventure.cpp:11:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   11 |         scanf(" %s",s);
      |         ~~~~~^~~~~~~~~

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