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; } };