AOJ 0560
JOI 2011 本選 1番「惑星探索」
二次元累積和の問題らしい。
左上の頂点の座標が(1,1)、右下の頂点の座標が(x,y)である長方形内に含まれる要素の数をnum[x][y][3]とすると、(num[x][y][0]は"J"の数、num[x][y][1]は"O"の数、num[x][y][2]は"I"の数)
左上の頂点の座標を(a,b)、右下の頂点の座標を(c,d)の長方形に含まれる要素数は、
num[c][d][a]-num[c][b-1][a]-num[a-1][d][a]+num[a-1][b-1][a]
(0<=a<3)
で計算される。
以下、ソースコード↓
#include <cstdio>
int
exist[1001][1001][3]={};
char
field[1001][1001];
int
m,n,Q;
int
main(){
scanf
(
"%d %d %d"
,&m,&n,&Q);
for
(
int
i=0;i<m;i++){
scanf
(
"%s"
,field[i]);
}
for
(
int
i=0;i<m;i++){
for
(
int
j=i;j<m;j++){
if
(field[i][0]==
'J'
){
exist[j][0][0]++;
}
else
if
(field[i][0]==
'O'
){
exist[j][0][1]++;
}
else
{
exist[j][0][2]++;
}
}
}
for
(
int
i=0;i<n;i++){
for
(
int
j=i;j<n;j++){
if
(field[0][i]==
'J'
){
exist[0][j][0]++;
}
else
if
(field[0][i]==
'O'
){
exist[0][j][1]++;
}
else
{
exist[0][j][2]++;
}
}
}
if
(field[0][0]==
'J'
){
exist[0][0][0]=1;
}
else
if
(field[0][0]==
'O'
){
exist[0][0][1]=1;
}
else
{
exist[0][0][2]=1;
}
for
(
int
i=1;i<m;i++){
for
(
int
j=1;j<n;j++){
for
(
int
k=0;k<3;k++){
exist[i][j][k]=exist[i][j-1][k];
}
for
(
int
k=0;k<=i;k++){
if
(field[k][j]==
'J'
){
exist[i][j][0]++;
}
else
if
(field[k][j]==
'O'
){
exist[i][j][1]++;
}
else
{
exist[i][j][2]++;
}
}
}
}
for
(
int
i=0;i<Q;i++){
int
a,b,c,d;
scanf
(
"%d %d %d %d"
,&a,&b,&c,&d);
if
(a>=2 && b>=2){
printf
(
"%d %d %d\n"
,exist[c-1][d-1][0]-exist[c-1][b-2][0]-exist[a-2][d-1] [0]+exist[a-2][b-2][0],exist[c-1][d-1][1]-exist[c-1][b-2][1]-exist[a-2][d-1][1]+exist[a-2][b-2][1],exist[c-1][d-1][2]-exist[c-1][b-2][2]-exist[a-2][d-1][2]+exist[a-2][b-2][2]);
}
else
if
(a<2){
printf
(
"%d %d %d\n"
,exist[c-1][d-1][0]-exist[c-1][b-2][0],exist[c-1][d-1][1]-exist[c-1][b-2][1],exist[c-1][d-1][2]-exist[c-1][b-2][2]);
}
else
{
printf
(
"%d %d %d\n"
,exist[c-1][d-1][0]-exist[a-2][d-1][0],exist[c-1][d-1][1]-exist[a-2][d-1][1],exist[c-1][d-1][2]-exist[a-2][d-1][2]);
}
}
return
0;
}
後半が滅茶苦茶になってしまった><