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

SRM 676 Div2 Medium BoardEscapeDiv2

問題

SRM 676 - TopCoder Wiki 二次元ボード上のゲームを考える. どんなゲームかは説明が面倒なので略.

解答

  • このゲームは2手読めば,どちらが勝つか分かる.
  • 初期状態でどこにも動けない.Bobの勝ち.
  • k=1.Aliceの勝ち
  • 出口に隣接しないセルに動ける.かつ,kが奇数.Aliceの勝ち(AliceはBobの反対の動きをし続ける)
  • そうでない場合,Bobの勝ち.(出口セルに移動する or Aliceと反対の動きをし続ける)

ただ,条件判定が色々あって,漏れが合ってミスを犯してしまった. min maxを使っても十分に計算可能そうなので,そちらのほうが実装が楽でよかったかもしれない.

class BoardEscapeDiv2
{
public:
  vector<string>board;
  int n, m;
  int dx[4] = {-1,0,1,0};
  int dy[4] = {0,1,0,-1};
  bool stacked(int r, int c){
    for(int i = 0; i < 4; i++){
      int nr = r + dy[i];
      int nc = c + dx[i];
      if (0 <= nr && nr < n &&
          0 <= nc && nc < m &&
          board[nr][nc] != '#') return false;
    }
    return true;
  }
  bool besideEscape(int r, int c){
    for(int i = 0; i < 4; i++){
      int nr = r + dy[i];
      int nc = c + dx[i];
      if (0 <= nr && nr < n &&
          0 <= nc && nc < m &&
          board[nr][nc] == 'E') return true;
    }
    return false;
  }
  string findWinner(vector <string> s, int k)
    {
      int r=0, c=0;
      n = s.size();
      m = s[0].size();
      board = s;
      for(int i = 0; i < n; i++){
        for(int j = 0; j < m; j++){
          if (board[i][j]=='T'){
            r = i;
            c = j;
          }
        }
      }
      if (stacked(r, c)) return "Bob";
      // cout << "hoge1" << endl;
      if (besideEscape(r, c)) return "Alice";
      // cout << "hoge2" << endl;
      if (k == 1) return "Alice";
      // cout << "hoge3" << endl;
      bool canMoveNotBesideEscape = false;
      for(int i = 0; i < 4; i++){
        int nr = r + dy[i];
        int nc = c + dx[i];
        if (0 <= nr && nr < n &&
            0 <= nc && nc < m &&
            board[nr][nc] != '#'){
          if (!besideEscape(nr, nc)) {
            // cout << "(nr, nc)=(" << nr << "," << nc << ")" << endl;
            canMoveNotBesideEscape = true;
          }
        }
      }
      // cout << "canMoveNotBesideEscape=" << canMoveNotBesideEscape << endl;
      if (canMoveNotBesideEscape) {
        if (k % 2 == 1) return "Alice";
        else return "Bob";
      } else {
        return "Bob";
      }
    }
};