1625 - Chessboard
Time Limit : 1 Second
Memory Limit : 128 MB
Submission: 501
Solved: 111
- Description
- Given an N*N(N<=1000)chessboard where you want to place chess knights.
On this chessboard you have to apply M(M<=100000) operations:
- Input
- The first line contains a single integer T, the number of test cases.
For each case,
The first line contains integer N, M.
The next M lines contain the operation in following form.
C a b x: place chess knight on cell(a,b), the value of the knight is x. (1<=a,b<=n, 1<=x<=100000)
It grants that cell(a,b) has no knight before the operation.
Q a b: answer the maximum value of knight which is connected with knight(a,b), include itself.
If cell (a,b)has no knight, just answer -1. A knight is directly connected with the knight on the left,
right, up and down. Two knights are connected if they have been directly connected or
interconnected through some other connected knights.
The initial chessboard is empty.
- Output
- For each question, output the answer in one line.
- sample input
-
1 3 7 C 2 2 1 Q 2 2 C 1 2 2 Q 2 2 C 3 3 3 Q 3 3 Q 1 1
- sample output
-
1 2 3 -1
- hint
- source
- The 8th(2013) ACM Programming Contest of HUST