AISing2019-C「Alternating Path」

• Alternating Path

考察

• ぱっと見上手く解く方法が思いつかない。なのでとりあえず愚直にDFSを書いてみる（BFSでもいいけど、DFSの方がメモ化して高速化しやすい）
• 愚直DFSのコード。# → .になってる時だけスコアが上がるのに気づかずにちょっと詰まった。（DFS書くのに30分もかかってるんだが）
• ジャッジが頑張ってくれて通らないかなーって思ったけど、まあ普通にTLEだった
• 経路みたいなメモ化再帰ができないかなー？って考えた。でもちょっと無理っぽい
• Ito Campusみたいに#を全部キューに突っ込んでからBFSする方法も考えた。けどだめ。何も関係ない
• DFSの愚直解は$O(H^2W^2)$。多分どこかで無駄な計算をしているのでそれをなんとかしたい
• 次は図を書いてみる。#から移動可能な箇所を埋めていくと、以下の図のようなグループ分けができる。
• もしかして、「同じグループに属する#は全部同じスコアになる」のでは？という気づきを得る。同じグループ内にある#から.へは確実に移動できるのでね。
• 一応実験もしてみたところ、上手く動いた。

解法

1. 盤面のループを回し、#を見つけたらそこから行ける部分をDFSで埋めていく。このとき、マスにはグループ番号を割り振る。同じグループの#からスタートすると、スコアは同じになるので再計算を防ぐためにmp[グループ番号]: スコアを作る。

コード

# include <bits/stdc++.h>
using namespace std;

# define int long long

const int dx[] = {1, -1, 0, 0};
const int dy[] = {0, 0, -1, 1};

int h, w;
char b[444][444]; // 盤面
int group[444][444]; // マスがどのグループに含まれるか。マスにグループIDを割り当てて判別する
map<int, int> mp; // mp[グループ番号]: そのグループの'#'が得られるスコア

// `#` -> '.' の順でいける部分を埋めていく
int rec(int y, int x, int t) {
  group[y][x] = t;
  int ret = 0;

  for (int i = 0; i < 4; i++) {
    int ny = y + dy[i], nx = x + dx[i];
    if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
    if (b[y][x] == b[ny][nx]) continue;
    if (group[ny][nx] != 0) continue;
    int cost = (b[ny][nx] == '.' ? 1 : 0); // 異動先が'.'ならスコアが入る
    ret += rec(ny, nx, t) + cost;
  }

  return ret;
}


signed main() {
  cin >> h >> w;
  for (int i = 0; i < h; i++) {
    cin >> b[i];
  }

  int ans = 0;
  int cnt = 1; // グループ番号
  for (int i = 0; i < h; i++) {
    for (int j = 0; j < w; j++) {
      if (b[i][j] == '#') {
        if (group[i][j] == 0) { // マスにグループ番号が割り振られていない場合
          int score = rec(i, j, cnt); // '#'からいける部分にグループ番号を割り当てる。
          ans += score;
          mp[cnt] = score; // グループ番号にスコアを登録する。これは、再計算を防ぐためにある
          cnt++; // グループ番号をインクリメント
        } else { // すでにグループ番号が割り振られている場合
          ans += mp[group[i][j]];
        }
      }
    }
  }

  cout << ans << endl;

  return 0;
}

もう少し考察してみる

• # →.の推移、.→#の推移を考える。このように推移するものに辺を引いていくと、自然とグループが出てくる。この発想結構自然だなーと思う。
• あと、グループ分けしたやつを連結成分っていうらしい。

要点

• グリッドもグラフのようにみることができる。
• グラフは移動できる部分を辺で結ぶと嬉しいことがある。例えば、辺で結ばれた部分は自由に移動できたりする。

メモ

• 連結成分を考えるのは定石らしい
• Union Findでも解けるらしい。つたさんはUFで解いてた
• Alternatingは交互のって意味らしい。Alternating Pathは、交互のパスって意味だったっぽい