Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <string>
- using namespace std;
- class bipart
- {
- public:
- bipart(int n, int m)
- {
- this->n = n;
- this->m = m;
- edges.resize(n + 1);
- }
- void AddEdge(int x, int y)
- {
- edges[x].push_back(y);
- }
- void GetCuplaj(vector<pair<int, int> > &ret)
- {
- vector<int> to(n+1), from(m+1);
- vector<bool> viz(n+1);
- bool cuplat = true;
- while(cuplat)
- {
- cuplat = false;
- fill(viz.begin(), viz.end(), false);
- for(int i = 1; i <= n; ++i)
- if(to[i] == 0 && cupleaza(i, viz, to, from))
- cuplat = true;
- }
- for(int i = 1; i <= n; ++i)
- if(to[i] != 0)
- ret.push_back({i, to[i]});
- }
- private:
- bool cupleaza(int nod, vector<bool> &viz, vector<int> &to, vector<int> &from)
- {
- if(viz[nod])
- return false;
- viz[nod] = true;
- for(auto v:edges[nod])
- if(from[v] == 0)
- {
- to[nod] = v;
- from[v] = nod;
- return true;
- }
- for(auto v:edges[nod])
- if(cupleaza(from[v], viz, to, from))
- {
- to[nod] = v;
- from[v] = nod;
- return true;
- }
- return false;
- }
- vector<vector<int> > edges;
- int n, m;
- };
- int n, m;
- char a[205][205];
- inline bool isLeftBlack(int i, int j)
- {
- if(j == 1 || a[i][j-1] == '.')
- return false;
- return true;
- }
- inline bool isRightBlack(int i, int j)
- {
- if(j == m || a[i][j+1] == '.')
- return false;
- return true;
- }
- inline bool isUpBlack(int i, int j)
- {
- if(i == 1 || a[i-1][j] == '.')
- return false;
- return true;
- }
- inline bool isDownBlack(int i, int j)
- {
- if(i == n || a[i+1][j] == '.')
- return false;
- return true;
- }
- inline int getIndRow(int i, int j)
- {
- return (i-1) * m + j;
- }
- inline int getIndCol(int i, int j)
- {
- return (i-1) * (m-1) + j;
- }
- int main()
- {
- cin >> n >> m;
- bipart graf((n-1) * m, n * (m-1));
- for(int i = 1; i <= n; ++i)
- cin >> (a[i]+1);
- int rasp = 0;
- // rasp = nr_negre - MIS = nr_negre - (noduri - cuplaj) = nr_negre - noduri + cuplaj
- for(int i = 1; i <= n; ++i)
- for(int j = 1; j <= m; ++j)
- {
- if(a[i][j] == '#')
- {
- rasp++; // patratica neagra
- if(isLeftBlack(i, j))
- rasp--; // pentru fiecare patratel numaram nodul din stanga
- if(isUpBlack(i, j))
- {
- rasp--; // pentru fiecare patratel numaram nodul de sus
- if(isLeftBlack(i, j))
- graf.AddEdge(getIndRow(i-1, j), getIndCol(i, j-1));
- if(isRightBlack(i, j))
- graf.AddEdge(getIndRow(i-1, j), getIndCol(i, j));
- }
- if(isDownBlack(i, j))
- {
- if(isLeftBlack(i, j))
- graf.AddEdge(getIndRow(i, j), getIndCol(i, j-1));
- if(isRightBlack(i, j))
- graf.AddEdge(getIndRow(i, j), getIndCol(i, j));
- }
- }
- }
- vector<pair<int, int> > cuplaj;
- graf.GetCuplaj(cuplaj);
- cout << rasp + (int)cuplaj.size();
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement