Hatena::Grouptopcoder

cou929のTopCoder日記

2009-12-27

SRM453.5 div1 (過去問)

10:09

Easy - MazeMaker

以前やったので問題文は省略. アプローチは単純なbfs. ミスしていた部分が3箇所あり, ひとつはbfsの中のループ内で配列インデックスを書き間違い. この部分のコードは毎回ほぼ同じなので, テンプレートを作っておこうと思います. 2つ目はループの終了条件の書き間違い. これはマクロで対応かなあ. tcでは使っている人も多い REP というマクロの導入を検討します. 3つ目はbfsの結果から最大のステップ数を探す際に, 'X'となっているセルをスキップし忘れていたこと. これはアルゴリズムのミスなので, 前の2つよりは罪が軽いかな. 対策としては, 2次元グリッド全体を出力する処理をテンプレートマクロにしておけば, デバッグが早くなってこういうミスに気づきやすくなるんじゃないかと考えています.

class MazeMaker {
public:
  int longestPath(vector <string> maze, int startRow, int startCol, vector <int> moveRow, vector <int> moveCol) {
    int ret = 0;
    int steps[maze.size()][maze[0].size()];
    const int INF = 10000;
    queue <int> q;

    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++)
        steps[i][j] = INF;

    q.push(startRow);
    q.push(startCol);
    steps[startRow][startCol] = 0;

    while (!q.empty()) {
      int cur_row = q.front();
      q.pop();
      int cur_col = q.front();
      q.pop();

      for (int i=0; i<moveRow.size(); i++) {
        int next_row = cur_row + moveRow[i];
        int next_col = cur_col + moveCol[i];
        if (0 <= next_row && next_row < maze.size() && 0 <= next_col && next_col < maze[0].size() &&
            maze[next_row][next_col] != 'X' && steps[next_row][next_col] == INF) {
          steps[next_row][next_col] = steps[cur_row][cur_col] + 1; // miss
          q.push(next_row);
          q.push(next_col);
        }
      }
    }

    for (int i=0; i<maze.size(); i++)
      for (int j=0; j<maze[0].size(); j++) // miss
        if (maze[i][j] != 'X')  // miss
          ret = max(ret, steps[i][j]);

    if (ret == INF) ret = -1;

    return ret;
  }
};