Advertisement
Guest User

Untitled

a guest
Apr 22nd, 2018
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.77 KB | None | 0 0
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <vector>
  4. using namespace std;
  5.  
  6. int n, m;
  7.  
  8. typedef vector<vector<int>> graph;
  9.  
  10. bool dfs(int v, graph &g, vector<bool> &used, vector<int> &match) {
  11.     if (used[v])
  12.         return false;
  13.     used[v] = true;
  14.     for(int to : g[v])
  15.         if (match[to] == -1 || dfs(match[to], g, used, match)) {
  16.             match[to] = v;
  17.             return true;
  18.         }
  19.     return false;
  20. }
  21.  
  22. void dfs_go(int v, bool move, graph &x, graph &y, vector<bool> &usedl, vector<bool> &usedr) {
  23.     if (move) {
  24.         if (usedr[v])
  25.             return;
  26.         usedr[v] = true;
  27.         for (int to : y[v])
  28.             dfs_go(to, 0, x, y, usedl, usedr);
  29.     }
  30.     else {
  31.         if (usedl[v])
  32.             return;
  33.         usedl[v] = true;
  34.         for (int to : x[v])
  35.             dfs_go(to, 1, x, y, usedl, usedr);
  36.     }
  37. }
  38.  
  39. struct answ {
  40.     int i, j, x;
  41.     char c;
  42.     answ(int x = 0, int i = 0, int j = 0, char c = ' ') : i(i), j(j), x(x), c(c) {}
  43. };
  44.  
  45. vector<answ> solve(graph &a, bool now) {
  46.     graph g(n + m - 1), rg(n + m - 1);
  47.     for (int i = 0; i < n; i++)
  48.         for (int j = 0; j < m; j++) {
  49.             if ((i + j) % 2 != now)
  50.                 continue;
  51.             if (a[i][j] != now)
  52.                 g[i + j].push_back(j + (n - 1 - i));
  53.         }
  54.     vector<int> match(n + m - 1, -1), ansl, ansr;
  55.     for (int i = 0; i < n + m - 1; i++) {
  56.         if (i % 2 != now)
  57.             continue;
  58.         vector<bool> used(n + m - 1);
  59.         dfs(i, g, used, match);
  60.     }
  61.     vector<bool> used(n + m - 1), usedl(n + m - 1), usedr(n + m - 1);
  62.     for (int i = 0; i < n + m - 1; i++)
  63.         if (match[i] != -1) {
  64.             rg[i].push_back(match[i]);
  65.             used[match[i]] = true;
  66.         }
  67.     for (int i = 0; i < n + m - 1; i++)
  68.         if (!used[i] && i % 2 == now)
  69.             dfs_go(i, 0, g, rg, usedl, usedr);
  70.     for (int i = 0; i < n + m - 1; i++) {
  71.         if (!usedl[i] && i % 2 == now)
  72.             ansl.push_back(i);
  73.         if (usedr[i] && (i % 2 == n % 2) == now)
  74.             ansr.push_back(i);
  75.     }
  76.     vector<answ> v;
  77.     char c = now ? 'B' : 'W';
  78.     for (auto i : ansl)
  79.         if (i < n)
  80.             v.push_back(answ(1, i, 0, c));
  81.         else
  82.             v.push_back(answ(1, n - 1, i - n + 1, c));
  83.     for (auto i : ansr)
  84.         if (i < n)
  85.             v.push_back(answ(2, n - 1 - i, 0, c));
  86.         else
  87.             v.push_back(answ(2, 0, i - n + 1, c));
  88.     return v;
  89. }
  90.  
  91. vector<answ> m_solve(graph &a) {
  92.     vector<answ> x = solve(a, 0), y = solve(a, 1);
  93.     x.insert(x.begin(), y.begin(), y.end());
  94.     return x;
  95. }
  96.  
  97. int main() {
  98.     ios_base::sync_with_stdio(0);
  99.     cin.tie(0); cout.tie(0);
  100.     cin >> n >> m;
  101.     graph a(n, vector<int>(m)), b(n, vector<int>(m));
  102.     for (int i = 0; i < n; i++)
  103.         for (int j = 0; j < m; j++) {
  104.             char c; cin >> c;
  105.             a[i][j] = (c != 'W');
  106.             b[i][j] = (c == 'W');
  107.         }
  108.     vector<answ> x = m_solve(a), y = m_solve(b);
  109.     bool oth = x.size() > y.size();
  110.     if (x.size() > y.size())
  111.         x = y;
  112.     cout << x.size() << endl;
  113.     for (auto i : x)
  114.         cout << i.x << " " << i.i + 1 << " " << i.j + 1 << " " << (oth ? char('W' + 'B' - i.c) : i.c) << "\n";
  115.     system("pause");
  116. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement