Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <algorithm>
- #include <iostream>
- #include <vector>
- using namespace std;
- int n, m;
- typedef vector<vector<int>> graph;
- bool dfs(int v, graph &g, vector<bool> &used, vector<int> &match) {
- if (used[v])
- return false;
- used[v] = true;
- for(int to : g[v])
- if (match[to] == -1 || dfs(match[to], g, used, match)) {
- match[to] = v;
- return true;
- }
- return false;
- }
- void dfs_go(int v, bool move, graph &x, graph &y, vector<bool> &usedl, vector<bool> &usedr) {
- if (move) {
- if (usedr[v])
- return;
- usedr[v] = true;
- for (int to : y[v])
- dfs_go(to, 0, x, y, usedl, usedr);
- }
- else {
- if (usedl[v])
- return;
- usedl[v] = true;
- for (int to : x[v])
- dfs_go(to, 1, x, y, usedl, usedr);
- }
- }
- struct answ {
- int i, j, x;
- char c;
- answ(int x = 0, int i = 0, int j = 0, char c = ' ') : i(i), j(j), x(x), c(c) {}
- };
- vector<answ> solve(graph &a, bool now) {
- graph g(n + m - 1), rg(n + m - 1);
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++) {
- if ((i + j) % 2 != now)
- continue;
- if (a[i][j] != now)
- g[i + j].push_back(j + (n - 1 - i));
- }
- vector<int> match(n + m - 1, -1), ansl, ansr;
- for (int i = 0; i < n + m - 1; i++) {
- if (i % 2 != now)
- continue;
- vector<bool> used(n + m - 1);
- dfs(i, g, used, match);
- }
- vector<bool> used(n + m - 1), usedl(n + m - 1), usedr(n + m - 1);
- for (int i = 0; i < n + m - 1; i++)
- if (match[i] != -1) {
- rg[i].push_back(match[i]);
- used[match[i]] = true;
- }
- for (int i = 0; i < n + m - 1; i++)
- if (!used[i] && i % 2 == now)
- dfs_go(i, 0, g, rg, usedl, usedr);
- for (int i = 0; i < n + m - 1; i++) {
- if (!usedl[i] && i % 2 == now)
- ansl.push_back(i);
- if (usedr[i] && (i % 2 == n % 2) == now)
- ansr.push_back(i);
- }
- vector<answ> v;
- char c = now ? 'B' : 'W';
- for (auto i : ansl)
- if (i < n)
- v.push_back(answ(1, i, 0, c));
- else
- v.push_back(answ(1, n - 1, i - n + 1, c));
- for (auto i : ansr)
- if (i < n)
- v.push_back(answ(2, n - 1 - i, 0, c));
- else
- v.push_back(answ(2, 0, i - n + 1, c));
- return v;
- }
- vector<answ> m_solve(graph &a) {
- vector<answ> x = solve(a, 0), y = solve(a, 1);
- x.insert(x.begin(), y.begin(), y.end());
- return x;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- cin.tie(0); cout.tie(0);
- cin >> n >> m;
- graph a(n, vector<int>(m)), b(n, vector<int>(m));
- for (int i = 0; i < n; i++)
- for (int j = 0; j < m; j++) {
- char c; cin >> c;
- a[i][j] = (c != 'W');
- b[i][j] = (c == 'W');
- }
- vector<answ> x = m_solve(a), y = m_solve(b);
- bool oth = x.size() > y.size();
- if (x.size() > y.size())
- x = y;
- cout << x.size() << endl;
- for (auto i : x)
- cout << i.x << " " << i.i + 1 << " " << i.j + 1 << " " << (oth ? char('W' + 'B' - i.c) : i.c) << "\n";
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement