naoya_t@topcoder

SRM368 Div1 Easy: JumpingBoard

過去問, 練習 | 03:04 |

3回目のsubmitでやっとSystem Testに通った。

• とりあえずBFSで探索
• 既に通った場所に戻ってきたら無限ループ可能なので-1を返す。が、BFSでやるなら通過履歴はちゃんとクリアしないと駄目
• メモ化しないとTLE

typedef vector<string> vs;
#define sz(a)  int((a).size())
#define mset(arr,val)  memset(arr,val,sizeof(arr))
#define found(s,e)  ((s).find(e)!=(s).end())

#define xy(x,y) (((x)<<6)|(y))
#define num(c) ((c)=='H')?-1:((c)-'0')

class JumpingBoard {
  vs orig;
  bool bd[50][50];
  int h,w;
  map<int,int> memo;
  
  int sub(int mv,int x,int y){
    int key=xy(x,y);
    if(found(memo,key)) return mv+memo[key];
    if(bd[x][y]) return -1;
    bd[x][y]=true;
    int a=num(orig[y][x]);
    int rmax=mv+1;
    if(x>=a && orig[y][x-a]!='H') {
      int r=sub(mv+1,x-a,y); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    if(x+a<w && orig[y][x+a]!='H') {
      int r=sub(mv+1,x+a,y); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    if(y>=a && orig[y-a][x]!='H') {
      int r=sub(mv+1,x,y-a); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    if(y+a<h && orig[y+a][x]!='H') {
      int r=sub(mv+1,x,y+a); if(r==-1) return -1;
      rmax=max(rmax,r);
    }
    bd[x][y]=false;
    memo[key]=rmax-mv;
    return rmax;
  }

 public:
  int maxJumps(vector<string> board) {
    orig=board;
    h=sz(board); w=sz(board[0]);
    mset(bd,0);
    return sub(0,0,0);
  }
};