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

SRM 576 Div2 Medium ArcadeManao

問題

高さがあるゲームのマップが与えられていて,指定された(空中にもある)フロアのみ訪れることが出来る. 横方向でフロアが続いていると自由に動けるが,縦方向にははしごが必要. 一番下のフロアから,指定された地点に行くために必要な最低のはしごの長さを答える問題.

解答

  • はしごの高さを1から順に大きくして全探索すれば良い.
  • 二分探索をすると効率的だが,しなくても十分速い.

こういうの頭では綺麗に考えられるんだが,実際にコードに落とすと汚くなる. たぶん,抽象的に考えていることを,具体的に落とす段階で躓いているのだと思う. これを回避するには具体的に落とす訓練をするしか無いような気がする. つまり数をこなす必用があると.

class ArcadeManao
{
public:
  int n;
  int m;
  int dx[4] = {0, 1, 0, -1};
  int dy[4] = {1, 0, -1, 0};
  bool canReach(vector<vector<char> > level, int ladder_len, int coinRow, int coinColumn){
    map<pair<int, int>, bool> memo;
    vector<vector<bool> > used = vector<vector<bool> >(n, vector<bool>(m, false));
    queue<pair<int, int> > q;
    for(int i = 0; i < m; i++) {
      q.push(make_pair(n-1, i));
      used[n-1][i] = true;
    }
    while(!q.empty()) {
      pair<int, int> p = q.front();
      q.pop();
      int r = p.first;
      int c = p.second;
      for(int i = 0; i < 4; i++) {
        int new_r = r, ladder;
        if (dy[i] != 0) {
          for(ladder = 1; ladder <= ladder_len &&
                r + dy[i] * ladder >= 0 && r + dy[i] * ladder < n && level[r + dy[i] * ladder][c] == '.'; ladder++);
          if (ladder <= ladder_len) new_r = r + dy[i] * ladder;
        }
        // int new_r = r + dy[i];
        int new_c = c + dx[i];
        if (0 <= new_r && new_r < n &&
            0 <= new_c && new_c < m &&
            used[new_r][new_c] == false &&
            level[new_r][new_c] == 'X'){
          q.push(make_pair(new_r, new_c));
          used[new_r][new_c] = true;
        }
      }
    }
    if (used[coinRow-1][coinColumn-1]) return true;
    return false;
  }
  int shortestLadder(vector <string> level, int coinRow, int coinColumn)
    {
      n = level.size();
      m = level[0].size();
      if (coinRow == n) return 0;
      vector<vector<char> > tmp = vector<vector<char> >(n, vector<char>(m, '.'));
      for(int i = 0; i < n; i++)for(int j= 0; j < m; j++) tmp[i][j] = level[i][j];
      // for(int i = 0; i < n; i++){
      //   for(int j = 0; j < m; j++) cout << tmp[i][j];
      //   cout << endl;
      // }
      // cout << endl;
      for(int ladder_len = 1; ladder_len < n; ladder_len++) {
      if (canReach(tmp, ladder_len, coinRow, coinColumn)) return ladder_len;
      }
      return 0;
    }
};