fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. const int N = 405;
  5.  
  6. struct edge {
  7.     int to, c;
  8. };
  9.  
  10. int n;
  11. string str[N];
  12. vector<edge> G[N];
  13. int vis[N];
  14. int cnt[2];
  15.  
  16. void dfs(int v, int c) {
  17.     vis[v] = c;
  18.     cnt[c]++;
  19.     for(auto e : G[v]) {
  20.         if(vis[e.to] == -1) dfs(e.to, e.c ^ c);
  21.         if(vis[e.to] != -1) assert(vis[e.to] == (e.c ^ c));
  22.     }
  23. }
  24.  
  25. void solve(int t) {
  26.     cin >> n;
  27.     for(int i = 0; i < n; i++) cin >> str[i];
  28.     for(int i = 0; i < 4 * n - 2; i++) G[i].clear();
  29.     for(int i = 0; i < n; i++) {
  30.         for(int j = 0; j < n; j++) {
  31.             int u = i + j, v = 2 * n - 1 + (i + (n - 1) - j);
  32.             G[u].push_back({v, str[i][j] == '.'});
  33.             G[v].push_back({u, str[i][j] == '.'});
  34.         }
  35.     }
  36.     fill(vis, vis + 4 * n - 2, -1);
  37.     int res = 0;
  38.     for(int i = 0; i < 4 * n - 2; i++) {
  39.         if(vis[i] == -1) {
  40.             cnt[0] = cnt[1] = 0;
  41.             dfs(i, 0);
  42.             res += min(cnt[0], cnt[1]);
  43.         }
  44.     }
  45.     cout << "Case #" << t << ": " << res << '\n';
  46. }
  47.  
  48. int main() {
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.  
  52.     int T;
  53.     cin >> T;
  54.     for(int t = 1; t <= T; t++) {
  55.         solve(t);
  56.     }
  57.  
  58. }
Runtime error #stdin #stdout 0s 4312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/9VLmKR
language:
C++14 (gcc 8.3)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!