fork download 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. #define int long long
  5. #define yes cout << "YES\n";
  6. #define no cout << "NO\n";
  7.  
  8.  
  9. void FastIO(){
  10.     ios_base::sync_with_stdio(false);
  11.     cin.tie(nullptr);
  12.     cout.tie(nullptr);
  13. }
  14.  
  15. void solve(){
  16.     int n,m; cin >> n >> m;
  17.  
  18.     vector<vector<int>> a(n+2, vector<int>(m+1,0));
  19.     vector<vector<int>> c(n+2, vector<int>(m+1,0));
  20.     vector<vector<int>> e(n+2, vector<int>(m+1,0));
  21.  
  22.     for(int i = 1; i <= n; i++){
  23.         for(int j = 1; j <= m; j++){
  24.             char ch; cin >> ch;
  25.             if(ch == 'a')
  26.                 a[i][j] = 1;
  27.             if(ch == 'c')
  28.                 c[i][j] = 1;
  29.             if(ch == 'e')
  30.                 e[i][j] = 1;
  31.         }
  32.     }
  33.  
  34.     for(int i = 1; i <= n; i++){
  35.         for(int j = 1; j <= m; j++){
  36.             a[i][j] += a[i][j-1];
  37.             c[i][j] += c[i][j-1];
  38.             e[i][j] += e[i][j-1];
  39.         }
  40.     }
  41.     for(int i = 1; i <= n; i++){
  42.         for(int j = 1; j <= m; j++){
  43.             a[i][j] += a[i-1][j];
  44.             c[i][j] += c[i-1][j];
  45.             e[i][j] += e[i-1][j];
  46.         }
  47.     }
  48.  
  49.     int q; cin >> q;
  50.     while(q--){
  51.         int r1,c1;
  52.         cin >> r1 >> c1;
  53.  
  54.         int r2,c2;
  55.         cin >> r2 >> c2;
  56.  
  57.         int la = a[r2][c2] - a[r2][c1-1] - a[r1-1][c2] + a[r1-1][c1-1];
  58.         int lc = c[r2][c2] - c[r2][c1-1] - c[r1-1][c2] + c[r1-1][c1-1];
  59.         int le = e[r2][c2] - e[r2][c1-1] - e[r1-1][c2] + e[r1-1][c1-1];
  60.  
  61.         int ans = min(la,lc);
  62.         ans = min(ans,le);
  63.  
  64.         cout << ans << '\n';
  65.     }
  66. }
  67.  
  68.  
  69. signed main(){
  70.     FastIO();
  71.  
  72.     int t = 1;
  73.     //cin >> t;
  74.  
  75.     while (t--){
  76.         solve();
  77.     }
  78.     return 0;
  79. }
  80.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
5 5
abcea
acedc
eacea
bcace
maher
4
1 1 4 5
2 2 4 4
1 3 3 5
5 1 5 5
stdout 
5
2
2
0
https://ideone.com/wujkhr
who
language:
C++14 (gcc 8.3)
created:
9 days 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!