首页 > 专题系列 > Java解POJ > POJ 2155 Matrix [解题报告] Java
2013
11-10

POJ 2155 Matrix [解题报告] Java

Matrix

问题描述 :

Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).

We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using “not” operation (if it is a ’0′ then change it into ’1′ otherwise change it into ’0′). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.

1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).

2. Q x y (1 <= x, y <= n) querys A[x, y].

输入:

The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.

The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.

输出:

For each querying output one line, which has an integer representing A[x, y].

There is a blank line between every two continuous test cases.

样例输入:

1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1

样例输出:

1
0
0
1

解题代码:

import java.util.Scanner;

public class Main {

	private static int[][] matrix = new int[1001][1001];
	private static int n;

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		int testNum = sc.nextInt();
		for (int i = 0; i < testNum; ++i) {
			matrix = new int[1001][1001];
			n = sc.nextInt();
			int t = sc.nextInt();
			for (int j = 0; j < t; ++j) {
				String c = sc.next();
				if (c.equals("C")) {
					int x1 = sc.nextInt();
					int y1 = sc.nextInt();
					int x2 = sc.nextInt();
					int y2 = sc.nextInt();
					change(x1 , y1 , 1);
					change(x1 , y2+1 , -1);
					change(x2+1 , y2+1 , 1);	
					change(x2+1 , y1 , -1);		
				} else if (c.equals("Q")) {
					int x = sc.nextInt();
					int y = sc.nextInt();
					int v = getSum(x, y) & 1;
					// System.out.println(getSum(x , y));
					if (v == 0)
						System.out.println(0);
					if (v == 1)
						System.out.println(1);
				}
			}
			System.out.println();
		}
	}

	public static void change(int x1, int y1, int x2, int y2) {

		for (int i = x1; i <= x2; ++i) {
			change(i, y1, 1);
			change(i, y2 + 1, -1);
		}
		// for (int i = x1; i <= x2; ++i) {
		// for (int j = y1; j <= y2; ++j) {
		//
		// if (matrix[i][j] == 0)
		// matrix[i][j] = 1;
		// else
		// matrix[i][j] = 0;
		// }
		// }
	}

	public static int lowbit(int i) {
		return i & -i;
	}

	public static void change(int i, int j, int value) {
		while (i <= n) {
			int temp = j;
			while (temp <= n) {
				matrix[i][temp] += value;
				temp += lowbit(temp);
			}
			i += lowbit(i);
		}
	}

	public static int getSum(int i, int j) {
		int sum = 0;
		while (i > 0) {
			int tmp = j;
			while (tmp > 0) {
				sum += matrix[i][tmp];
				tmp -= lowbit(tmp);
			}
			i -= lowbit(i);
		}
		return sum;
	}

}

  1. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。