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

SRM 637 Div2 Medium PathGameDiv2

問題

SRM 637 - TopCoder Wiki

2行しかないチェスボードを考える(列は1以上). 各セルは黒か白に塗られていて,一番左のセルから一番右のセルまで白のセルを辿って到達できる. 移動は上下か横の隣接する白セルにのみ移動できる. この性質を保ったまま,白セルを黒セルに置き換える時,置き換えることの出来る最大セル数を求める問題.

解答

  • 最短距離を求めて,それ以外の白セルを塗りつぶす.
  • 今いるセルの右セルが白ならば上下に移動するよりも右セルに移動するのが最適.
  • そのようにして最短路を求めることが出来る.
  • もちろん,2行あるうちのどちらを選ぶかで距離が変わるので両方試して距離の短い方を選ぶ.
  • 後は,残りの白セルを塗りつぶせば答えが求まる.
class PathGameDiv2
{
public:
  int calc(vector <string> board)
    {
      int res = 0;
      int i;
      int n = board[0].size();
      for (int row = 0; row < 2; row++){
        int cur = row;
        if (board[cur][0] == '#') continue;
        int count = 0;
        for (i = 0; i < n; i++) {
          if (i == n-1 || board[cur][i+1] == '.') {
            if (board[(cur+1)%2][i] == '.') count++;
          }else {
            cur = (cur + 1) % 2;
          }
        }
        res = max(res, count);
      }
      return res;
    }
};