fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define Long long long
  6. #define bint __int128
  7. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  8.  
  9. int c;
  10. vector<vector<int>> adj;
  11.  
  12. vector<bool> vis;
  13. vector<int> comp;
  14. void dfs(int v) {
  15.     vis[v] = true;
  16.     comp.push_back(v);
  17.     for (int u : adj[v]) {
  18.         if (vis[u]) continue;
  19.         dfs(u);
  20.     }
  21. }
  22.  
  23. int solve() {
  24.     int ans = 0;
  25.     queue<int> q;
  26.     vis.assign(c, false);
  27.     vector<int> side(c, -1);
  28.     for (int v = 1; v < c; ++v) {
  29.         if (not vis[v]) {
  30.             comp.clear(), dfs(v);
  31.             q.push(v), side[v] = 0;
  32.             while ( not q.empty() ) {
  33.                 int p = q.front();
  34.                 q.pop();
  35.                 for (int u : adj[p]) {
  36.                     if (side[u] == -1) {
  37.                         side[u] = side[p] ^ 1;
  38.                         q.push(u);
  39.                     }
  40.                 }
  41.             }
  42.             int l = 0, r = 0;
  43.             for (int node : comp) {
  44.                 if (side[node] == 0) ++l;
  45.                 else ++r;
  46.             }
  47.             ans += max(l, r);
  48.         }
  49.     }
  50.     return ans;
  51. }
  52.  
  53. void get_shit_done() {
  54.     int n, m;
  55.     cin >> n >> m;
  56.  
  57.     vector< vector<char> > g( n + 1, vector<char>(m + 1) );
  58.     for (int i = 1; i <= n; ++i) {
  59.         for (int j = 1; j <= m; ++j) {
  60.             cin >> g[i][j];
  61.         }
  62.     }
  63.  
  64.     int length;
  65.     cin >> length;
  66.  
  67.     string s;
  68.     cin >> s;
  69.  
  70.     c = 1;
  71.     vector< vector<int> > gl( n + 1, vector<int>(m + 1, -1) );
  72.     for (int i = 1; i <= n; ++i) {
  73.         for (int j = 1; j <= m; ++j) {
  74.             int at = j, p = 0;
  75.             while ( p < length and at <= m and g[i][at] == s[p] ) ++at, ++p;
  76.             if (p == length) {
  77.                 for (int k = j; k < at; ++k) gl[i][k] = c;
  78.                 ++c;
  79.             }
  80.             j = max(j, at - 1);
  81.         }
  82.     }
  83.  
  84.     vector< vector<int> > gr( n + 1, vector<int>(m + 1, -1) );
  85.     for (int j = 1; j <= m; ++j) {
  86.         for (int i = 1; i <= n; ++i) {
  87.             int at = i, p = 0;
  88.             while ( p < length and at <= n and g[at][j] == s[p] ) ++at, ++p;
  89.             if (p == length) {
  90.                 for (int k = i; k < at; ++k) gr[k][j] = c;
  91.                 ++c;
  92.             }
  93.             i = max(i, at - 1);
  94.         }
  95.     }
  96.  
  97.     adj.assign(c, {});
  98.     for (int i = 1; i <= n; ++i) {
  99.         for (int j = 1; j <= m; ++j) {
  100.             if ( gl[i][j] != -1 and gr[i][j] != -1 ) {
  101.                 adj[ gl[i][j] ].push_back( gr[i][j] );
  102.                 adj[ gr[i][j] ].push_back( gl[i][j] );
  103.             }
  104.         }
  105.     }
  106.  
  107.     cout << solve() << '\n';
  108. }
  109.  
  110. signed main() {
  111.     _3bkarm
  112.     freopen("grid.in", "r", stdin);
  113.  
  114.     int ts = 1;
  115.     cin >> ts;
  116.     while (ts--) {
  117.         get_shit_done();
  118.     }
  119.  
  120.     return 0;
  121. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/wmZNQZ
language:
C++14 (clang 8.0)
created:
1 day ago
visibility:
public

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!