TopCoder SRM 576 Div1 Easy: ArcadeManao

解法

二分探索 + UnionFind

コード

#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <typeinfo>
#include <fstream>

using namespace std;

class UnionFind {
 public:
  UnionFind(const int &x) { init(x); }
  UnionFind(const UnionFind &uf) {
    this->cnt = uf.cnt;
    this->n = uf.n;
    copy(uf.par.begin(), uf.par.end(), back_inserter(this->par));
  }
  inline int find(const int &x) {
    return par[x] < 0 ? x : par[x] = find(par[x]);
  }
  inline bool same(const int &x, const int &y) { return find(x) == find(y); }
  inline bool unite(int x, int y) {
    if ((x = find(x)) == (y = find(y))) return false;
    --cnt;
    if (par[x] > par[y]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
    return true;
  }
  inline int count() const { return cnt; }
  inline int count(int x) { return -par[find(x)]; }

  // private:
  vector<int> par;
  int n, cnt;
  void init(const int &x) { par.assign(cnt = n = x, -1); }
  UnionFind() {}
};

class ArcadeManao {
 public:
  int shortestLadder(vector<string> level, int coinRow, int coinColumn) {
    if (coinRow == level.size()) return 0;
    coinColumn--;
    coinRow--;
    int N = level.size();
    int M = level[0].size();
    int high = max(N, M);
    int low = 0;
    UnionFind uf(N * M);
    for (int n = 0; n < N; ++n) {
      for (int m = 0; m < M - 1; ++m) {
        if (level[n][m] == level[n][m + 1] && level[n][m] == 'X') {
          uf.unite(n * M + m, n * M + m + 1);
        }
      }
    }

    while (high > low + 1) {
      UnionFind tmp_uf(uf);
      int mid = (high + low) / 2;
      for (int n = 0; n < N; ++n) {
        for (int m = 0; m < M; ++m) {
          for (int i = 0; i <= mid; ++i) {
            if (n + i < N && level[n][m] == level[n + i][m] &&
                level[n][m] == 'X') {
              tmp_uf.unite(n * M + m, (n + i) * M + m);
            }
          }
        }
      }
      if (tmp_uf.same((N - 1) * M, coinRow * M + coinColumn)) {
        high = mid;
      } else {
        low = mid;
      }
    }
    return high;
  }
};