2013
11-10

# Counting Black

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.

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.

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

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


7
6

//* @author 洪晓鹏<[email protected]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */>import java.util.Scanner;

public class Main {
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int num = in.nextInt();
int[][] grids = new int[101][101];
for(int i = 0; i< num; i++)
{
String color = in.next();
int x = in.nextInt();
int y = in.nextInt();
int l = in.nextInt();
if(color.equals("BLACK"))
{
for(int j = x; j< x+l; j++)
{
for(int k = y; k< y+l; k++)
{
grids[j][k] = 1;
}
}
}
if(color.equals("WHITE"))
{
for(int j = x; j< x+l; j++)
{
for(int k = y; k< y+l; k++)
{
grids[j][k] = 0;
}
}
}
if(color.equals("TEST"))
{
int count = 0;
for(int j = x; j< x+l; j++)
{
for(int k = y; k< y+l; k++)
{
if(grids[j][k] == 1)
count++;
}
}
System.out.println(count);
}
}
}
}

1. 在方法1里面：

//遍历所有的边，计算入度
for(int i=0; i<V; i++)
{
degree = 0;
for (j = adj .begin(); j != adj .end(); ++j)
{
degree[*j]++;
}
}

为什么每遍历一条链表，要首先将每个链表头的顶点的入度置为0呢？
比如顶点5，若在顶点1、2、3、4的链表中出现过顶点5，那么要增加顶点5的入度，但是在遍历顶点5的链表时，又将顶点5的入度置为0了，那之前的从顶点1234到顶点5的边不是都没了吗？

2. 可以根据二叉排序树的定义进行严格的排序树创建和后序遍历操作。如果形成的排序树相同，其树的前、中、后序遍历是相同的，但在此处不能使用中序遍历，因为，中序遍历的结果就是排序的结果。经在九度测试，运行时间90ms，比楼主的要快。

3. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish