読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

codingame - Bender, a depressed robot

ループ判定が面倒
自分は同じ所を同じ向きで通った場合にループ判定を出すようにした.
しかしこれだけでは最後のテストケースが落ちるので20回以上同じ所を同じ向きで通った場合判定を出すようにした.

struct P
{
  int x,y;
  P(){};
  P(int x, int y): x(x), y(y){};
};

int main()
{
  int l,c; cin >> l >> c;
  //cerr << l << " " << c << endl;
  int n = l*c;
  int dx[] = {0,1,0,-1,0};
  int dy[] = {0,0,1,0,-1};
  char cmd[] = {' ','S','E','N','W','B','I','T','@','$','X','#'};
  string out[] = {"","SOUTH\n","EAST\n","NORTH\n","WEST\n"};
  // 0 : space, 1-4 : dir, 5-7 : cmd, 8-9 start&goal 10-11 : obstacle
  vector<vector<int> > T(l,vector<int>(c,0));
  vector<vector<int> > U(l,vector<int>(c,0));
  REP(i,l)
  {
    string s; getline(cin,s);
    if(s=="") {i--; continue;}
    //cerr << s << endl;
    REP(j,c) REP(k,12) if(s[j]==cmd[k]) T[i][j] = k;
  }

  string ans = "";
  int dir = 1; P p;
  bool loop = false, reverse = false, beer = false;
  REP(i,l) REP(j,c) if(T[i][j] == 8) p = P(i,j);
  while(T[p.x][p.y] != 9)
  {
    int now = T[p.x][p.y];
    //cerr << cmd[now] << " " << p.x << " " << p.y << endl;
    int b = p.x*c+p.y;
    if(now >= 1 && now <=4) dir = now;
    if(now == 5) beer = !beer;
    if(now == 6) reverse = !reverse;
    if(now == 7)
    {
      for(int i=(b+1)%n;i!=b;i=(i+1)%n) if(T[i/c][i%c]==7)
      {
        //cerr << i << " " << n << endl;
        p.x = i/c;
        p.y = i%c;
        break;
      }
    }
    if(T[p.x+dx[dir]][p.y+dy[dir]]>=10)
    {
      if(T[p.x+dx[dir]][p.y+dy[dir]]==10 && beer)
      {
        T[p.x+dx[dir]][p.y+dy[dir]] = 0;
      }
      else
      {
        if(reverse)
        {
          DOWN(i,4,1) if(T[p.x+dx[i]][p.y+dy[i]] < 10)
          {
            dir = i;
            break;
          }
        }
        else
        {
          FOR(i,1,4) if(T[p.x+dx[i]][p.y+dy[i]] < 10)
          {
            dir = i;
            break;
          }
        }
      }
    }
    if(dir+reverse*10+beer*100==U[p.x][p.y]%1000 && U[p.x][p.y]/1000 > 20)
    {
      loop = true;
      break;
    }
    U[p.x][p.y] = (U[p.x][p.y]/1000+1)*1000+dir+reverse*10+beer*100;
    p.x += dx[dir];
    p.y += dy[dir];
    ans += out[dir];
  }
  cout << ((loop)?"LOOP\n":ans);
  return 0;
}