Robots in a Grid - #634 div3 f

#cycle 復元 #pair #pii #ダブリング

各頂点出次数 1 より, cycle から外に矢印は出ない
連結成分ごとに考える
各連結成分に cycle は 1 つ

まず, black 関係ない答え

cycle のサイズの合計

それだけ求めるコード

map<pii, pii> G;
vector<vector<char> > table;
map<pii, int> seen;
pii pos = pii(-1, -1); // cycle 中に含まれる頂点 pos
stack<pii> hist; // 訪問履歴

void dfs(pii v, pii p) {
  seen[v] = 1;
  hist.push(v);
  pii nv = G[v];
  if (seen[nv] == 2) return;
  if (seen[nv] == 1) { // cycle を検出
    pos = nv;
    return;
  }
  dfs(nv, v);
  if (pos != pii(-1, -1)) return;
  hist.pop();
  seen[v] = 2;
}

void solve() {
  G.clear();
  seen.clear();

  int n, m;
  cin >> n >> m;

  table = c = vector<vector<char> >(n, vector<char>(m));
  rep(i, n) rep(j, m) cin >> table[i][j];
  rep(i, n) rep(j, m) cin >> c[i][j];

  // U, R, D, L
  int dy[] = {-1, 0, 1, 0};
  int dx[] = {0, 1, 0, -1};
  char ch[] = {'U', 'R', 'D', 'L'};
  rep(i, n) rep(j, m) {
    rep(k, 4) {
      if (ch[k] == c[i][j]) {
        G[pii(i, j)] = pii(i + dy[k], j + dx[k]);
      }
    }
  }

  int ans = 0;
  rep(i, n) rep(j, m) {
    pos = pii(-1, -1);
    dfs(pii(i, j), pii(-1, -1));
    vector<pii> cycle;
    while (!hist.empty()) {
      pii t = hist.top();
      cycle.eb(t);
      hist.pop();
      if (t == pos) { // cycle にはまった
        ans += sz(cycle);
        // break しない, cycle の外の経路も
      }
    }
  }
  cout << ans << '\n';
}

black 関係なく最大にした上で black を最大にする

各 cycle 上の頂点に 0 から番号をつける
cycle の外の頂点には, cycle から近い方から -1 mod (cycle のサイズ) の番号をつけていく

黒だけで, 数字が何種類あるか求めればいい

ソースコード
有向辺である
https://codeforces.com/contest/1335/submission/76933542

十分時間がたった後どこにいるか見る方が楽
https://codeforces.com/contest/1335/submission/76926285