AOJ 0560 - Planetary Exploration

久しぶりに番兵法を用いました．
方針はdp[y][x][t]を(y, x')()で地形がtとなる個数とします．
すると，(x1, y) (x2, y)間()の地形tの個数はdp[y][x2] - dp[y][x1-1]となります．((1, 1)起点なので負になりません．嬉しいですね)
(x1, y1) (x2, y2)間ではyを変えながら足していけば終わりです．
計算量はO(WH)でしょう．

#include<iostream>

int H, W, K;
int dp[1001][1001][3];

int solve(int x1, int y1, int x2, int y2, int type){
	int res = 0;
	for(int y=y1;y<=y2;y++){
		res += dp[y][x2][type] - dp[y][x1-1][type];
	}
	return res;
}

int main(){
	std::cin >> H >> W >> K;
	for(int y=1;y<=H;y++){
		for(int x=1;x<=W;x++){
			char c;
			std::cin >> c;
			if(c == 'J')dp[y][x][0]++;
			if(c == 'O')dp[y][x][1]++;
			if(c == 'I')dp[y][x][2]++;
			for(int i=0;i<3;i++){
				dp[y][x][i] += dp[y][x-1][i];
			}
		}
	}

	while(K--){
		int x1, y1, x2, y2;
		std::cin >> y1 >> x1 >> y2 >> x2;
		std::cout << solve(x1, y1, x2, y2, 0);
		for(int t=1;t<3;t++){
			std::cout << " " << solve(x1, y1, x2, y2, t);
		}
		std::cout << "\n";
	}
}