/* Author : Mychecksdead */
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define MOD (1000000000+7)
#define MOD1 (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
const int N = 1e6+100, M = 1e5+10, K = 18;
int n, m, tot = 0;
string s[N];
vector<int> g[N];
vector<pair<int, int>> segdown;
vector<pair<int, int>> segright;
vector<bool> vis(N);
vector<int> white;
vector<int> nigga;
pair<int, int> dfs(int v, bool col){
if(v <= n*m && v > segdown.size()) return {0, 0};
if(v > n*m && v > segright.size()+n*m) return {0, 0};
vis[v] = 1;
tot++;
pair<int, int> dpv = {1, 0};
for(int u: g[v]){
if(!vis[u]){
auto dpu = dfs(u, col^1);
dpv.first += min(dpu.first, dpu.second);
dpv.second += dpu.first;
taken = 1;
}
}
return dpv;
}
void solve(){
cin >> n >> m;
for(int i = 0; i < n; ++i) cin >> s[i];
vector<vector<vector<int>>> c(n);
for(int i = 0; i < n; ++i) c[i].resize(m);
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
if(s[i][j] == '0' && s[i - 1][j] == '1'){
int idx = segdown.size() + 1;
for(int k = i; k < n; ++k){
if(s[k][j] == '1') break;
c[k][j].pb(idx);
}
segdown.pb({i, j});
}
if(s[i][j] == '0' && s[i][j - 1] == '1'){
int idx = n*m+segright.size()+1;
for(int k = j; k < m; ++k){
if(s[i][k] == '1') break;
c[i][k].pb(idx);
}
segright.pb({i, j});
}
}
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < m; ++j){
if(s[i][j] == '0'){
g[c[i][j][0]].pb(c[i][j][1]);
g[c[i][j][1]].pb(c[i][j][0]);
}
}
}
int ans = 0;
for(int i = 1; i <= 2*n*m; ++i){
if(!vis[i]){
tot = 0;
pair<int, int> dpv = dfs(i, 0);
if(tot == 1) ans++;
else ans += min(dpv.first, dpv.second);
}
}
cout << ans;
return;
if(white.size() > nigga.size()) white.swap(nigga);
cout << white.size() << '\n';
for(auto w: white){
if(w >= n*m){
cout << segright[w - n*m - 1].first + 1 << ' ' << segright[w - n*m - 1].second << ' '<< "DESNO\n";
}else{
cout << segdown[w - 1].first << ' ' << segdown[w - 1].second + 1 << ' '<< "DOLJE\n";
}
}
}
int main(){
cin.tie(0); ios::sync_with_stdio(0);
int tt = 1, aa;
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
// cin >> tt;
while(tt--){
solve();
// en;
}
cerr<<"time taken : "<<(float)clock()/CLOCKS_PER_SEC<<" seconds\n";
return 0;
}
Compilation message
skandi.cpp: In function 'std::pair<int, int> dfs(int, bool)':
skandi.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
24 | if(v <= n*m && v > segdown.size()) return {0, 0};
| ~~^~~~~~~~~~~~~~~~
skandi.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
25 | if(v > n*m && v > segright.size()+n*m) return {0, 0};
| ~~^~~~~~~~~~~~~~~~~~~~~
skandi.cpp:35:7: error: 'taken' was not declared in this scope; did you mean 'tan'?
35 | taken = 1;
| ^~~~~
| tan
skandi.cpp: In function 'int main()':
skandi.cpp:101:15: warning: unused variable 'aa' [-Wunused-variable]
101 | int tt = 1, aa;
| ^~
