Submission #404609

#	Time	Username	Problem	Language	Result	Execution time	Memory
404609		cadmiumsky	Awesome Arrowland Adventure (eJOI19_adventure)	C++14	100 / 100	41 ms	8528 KiB

adventure

#include <iostream>

using namespace std;

char dir[505][505][4];
char orig[505][505];
int arriv[505][505][4];
int n,m;
int dirx[4]={-1,0,1,0};
int diry[4]={0,1,0,-1};

class QUEUE {
  int qx[262144];
  int qy[262144];
  int qp[262144];
  int l,r;
  public:
    void reset() {
      l=0;
      r=0;
    }
    void pushb(int x,int y,int p) {
      qx[r]=x;
      qy[r]=y;
      qp[r++]=p;
      r&=262143;
    }
    void pushf(int x,int y, int p) {
      l=(l-1)&262143;
      qx[l]=x;
      qy[l]=y;
      qp[l]=p;
    }
    void pop() {
      l=(l+1)&262143;
    }
    int topx() {
      return qx[l];
    }
    int topy() {
      return qy[l];
    }
    int topp() {
      return qp[l];
    }
    bool empty() {
      return l==r;
    }
}que;

static int dbfs() {
  if(que.empty())
    return -1;
  int x=que.topx(),y=que.topy(),p=que.topp();
  que.pop();
  if(x==n && y==m)
    return arriv[x][y][p];
  if(p==4)
    return dbfs();
  int c=dir[x][y][p];
  //cout << x <<' '<< y <<' '<< p << '\n';
  //cout << dirx[c] <<' '<< diry[c] << ' '<< c << "\n\n";
  if(c==-1)
    return dbfs();
  dir[x][y][p]=-1;
  que.pushf(x+dirx[c],y+diry[c],0);
  arriv[x+dirx[c]][y+diry[c]][0]=arriv[x][y][p];
  if(p!=3) {
    que.pushb(x,y,p+1);
    arriv[x][y][p+1]=arriv[x][y][p]+1;
  }
  return dbfs();
}

int main() {
  cin >> n >> m;
  for(int i=1; i<=n; i++) {
    for(int j=1; j<=m; j++) {
      cin >> dir[i][j][0];
      if(dir[i][j][0]=='N') 
        dir[i][j][0]=0;
      else if(dir[i][j][0]=='E')
        dir[i][j][0]=1;
      else if(dir[i][j][0]=='S')
        dir[i][j][0]=2;
      else if(dir[i][j][0]=='W')
        dir[i][j][0]=3;
      else
        dir[i][j][0]=-1;
      if(dir[i][j][0]!=-1) {
        for(int h=1; h<4; h++)
          dir[i][j][h]=((dir[i][j][h-1]+1)&3);
      }
    }
  }
  for(int i=0; i<=n+1; i++) {
    for(int j=0; j<4; j++)
      dir[i][0][j]=dir[i][m+1][j]=-1;
  }
  for(int i=0; i<=m+1; i++) {
    for(int j=0; j<4; j++)
      dir[n+1][i][j]=dir[0][i][j]=-1;
  }
  if(dir[1][1][0]==-1) {
    cout << -1 <<'\n';
    return 0;
  }
  que.reset();
  que.pushb(1,1,0);
  cout << dbfs() <<'\n';
}

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