POJ 1656 Counting Black（我的水題之路——表格塗色）

Counting Black

Time Limit: 1000MS	Memory Limit: 10000K
Total Submissions: 8499	Accepted: 5469

Description

There is a board with 100 * 100 grids as shown below. The left-top gird is denoted as (1, 1) and the right-bottom grid is (100, 100). 

We may apply three commands to the board: 

1.	WHITE  x, y, L     // Paint a white square on the board, 

                           // the square is defined by left-top grid (x, y)

                           // and right-bottom grid (x+L-1, y+L-1)



2.	BLACK  x, y, L     // Paint a black square on the board, 

                           // the square is defined by left-top grid (x, y)

                           // and right-bottom grid (x+L-1, y+L-1)



3.	TEST     x, y, L    // Ask for the number of black grids 

                            // in the square (x, y)- (x+L-1, y+L-1)       

In the beginning, all the grids on the board are white. We apply a series of commands to the board. Your task is to write a program to give the numbers of black grids within a required region when a TEST command is applied. 

Input

The first line of the input is an integer t (1 <= t <= 100), representing the number of commands. In each of the following lines, there is a command. Assume all the commands are legal which means that they won't try to paint/test the grids outside the board.

Output

For each TEST command, print a line with the number of black grids in the required region.

Sample Input

5
BLACK 1 1 2
BLACK 2 2 2
TEST 1 1 3
WHITE 2 1 1
TEST 1 1 3
      

Sample Output

7
6      

Source

POJ Monthly--2004.05.15 Liu [email protected]

有一個100*100的方格，對其進行N次操作，操作類型分為BLACK、WHITE、TEST三種。如果是BLACK，就将(x, y)到（x+l-1,y+l-1）之間的區域變成黑色，如果是WHITE，則讓其為白色，如果是TEST，就計算這個區域内有多少個黑色方塊，并且輸出。

由于資料給的弱，是以用的方法是暴力模拟

注意： 1）如果是高資料，這種方法會TLE，可以使用二維線段樹進行塗色功能。

代碼（1AC）：

#include <cstdio>
#include <cstdlib>
#include <cstring>

int count[110][110];

int main(void){
    int casenum ,ii;
    char oprator[10];
    int x, y, l;
    int i, j;
    int num, value;

    while (scanf("%d", &casenum) != EOF){
        getchar();
        memset(count, 0, sizeof(count));
        for (ii = 0; ii < casenum; ii++){
            scanf("%s%d%d%d", oprator, &x, &y, &l);
            getchar();
            if (!strcmp(oprator, "TEST")){
                value = -1;
                num = 0;
            }
            else if (!strcmp(oprator, "WHITE")){
                value = 0;
            }
            else if (!strcmp(oprator, "BLACK")){
                value = 1;
            }
            for (i = x; i <= x + l - 1; i++){
                for (j = y; j <= y + l - 1; j++){
                    if (value == -1){
                        if (count[i][j] == 1){
                            num ++;
                        }
                    }
                    else{
                        count[i][j] = value;
                    }
                }
            }
            if (value == -1){
                printf("%d\n", num);
            }
        }
    }
    return 0;
}