
ZOJ Problem Set  2411
A single player game is played on a grid chessboard with some colored beads on. In each round, the player can click on two grids of the chessboard. If the two grids both have beads of the same color, and a line with no more than two turns could be drawn to connect the two beads, the two beads will both disappear from the chessboard. Note that the line must not pass through any other beads. Figure 1: Valid clicks that will erase the two beads Given the information of a chessboard and the player's clicks in each round, you are required to calculate how many beads will disappear. InputThe input consists of several test cases. The first line of each case contains two numbers N and M (1 <= N, M <= 100), indicating the dimensions of the chessboard. Then N lines follow, each represents a row of the chessboard. The positive numbers represent different colors of beads, and zero represents an empty grid. Then there is a positive number T followed by T lines of input which describe the clicks of all T rounds. Each line contains four numbers x1, y1, x2, y2 which are the positions (x1, y1) and (x2, y2) of the two clicks on the chessboard (the northwest corner is at (1, 1)). Output For each case, print in one line the number of beads disappeared. Sample Input 3 4 1 1 2 2 3 3 4 4 2 2 1 1 6 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 3 4 1 2 1 2 3 4 3 4 2 1 2 1 6 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 3 4 1 2 1 2 1 1 2 2 2 2 1 1 3 2 3 2 4 2 2 3 3 3 2 1 4 2 3 0 0 0 0 0 0 2 1 1 1 1 1 1 1 2 0 0 Sample Output 12 0 6 0
Author: ZHENG, Jianqiang Source: Zhejiang University Local Contest 2005 