首页 > 专题系列 > Java解POJ > POJ 1656 Counting Black [解题报告] Java
2013
11-10

POJ 1656 Counting Black [解题报告] Java

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]>
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