AOJ0560 惑星探査

解法

---

二次元累積和を実装していい感じにやる

ソース

---

#include<iostream>  
#include<vector>  
#include<algorithm>  
#include<string>  
   
using namespace std;  
int mas[1001][1001][3];  
int main(){  
   
  int M, N, K;  
  string tmp = "JOI";  
   
  cin >> M >> N;  
  cin >> K;  
  for(int i = 1 ; i <= M ; i++ ){  
    for(int j = 1 ; j <= N ; j++ ){  
      char c;  
      cin >> c;  
      for(int k = 0 ; k < 3 ; k++ ){  
        mas[i][j][k] = mas[i-1][j][k] + mas[i][j-1][k] - mas[i-1][j-1][k];  
      }  
      mas[i][j][tmp.find(c)]++;  
    }  
  }  
  for(int i = 0 ; i < K ; i++ ){  
    int a, b, c, d;  
    cin >> a >> b >> c >> d;  
    for(int j = 0 ; j < 3 ; j++ ){  
      cout << (j?" ":"") << mas[c][d][j] + mas[a-1][b-1][j] - mas[a-1][d][j] - mas[c][b-1][j];  
    }  
    cout << endl;  
  }  
}