PROB11 - Truy vấn ma trận
English
Given a table of squares with N rows and M columns, each square has a value of 1 or 2. The table of tiles can be moved in one of four Up-Down-Left-Right ways:
- Up: the lines move up 1 line, the top line moves to the bottom.
- Down: the lines move down 1 line, the bottom line moves to the top
- Left : the columns move to the left 1 column, the leftmost column moves to the right column.
- Right : the columns move to the right 1 column, the right column moves to the left most column.
Given T queries of one of four types:
- 1 x : execute x Down commands with the given table of squares.
- 2 x : execute x Right commands with the given table of squares.
- 3 x : execute x Up command with the given table of squares.
- 4 x : execute x Left commands with the given grid of squares.
For each query give the number of 2×2 squares whose sum is 4 or 8.
Input
The first line is the number of test cases T of the problem.
The first line of each test case is 3 numbers N, M, K. The number of rows, the number of columns of the matrix and the number of queries, respectively.
Next N lines, each containing M numbers (1, 2) indicating the value at position (i, j)
Next K lines, each line is a query in the above format.
Output
Each test case is printed on 1 line, starting with the character '#', followed by the test case number, followed by 1 space, and finally K results for each query. (Each result is separated by 1 space.)
Constraints
1 <= T <= 70
3 <= N, M <= 2000
1 <= K <= 10^5
1 <= x <= 10^9
Example
Input: 1 4 5 5 1 1 2 2 2 1 1 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 2 1 3 2 1 2 2 Output: #1 5 4 2 3 2
Vietnamese
Cho một bảng ô vuông N hàng M cột, mỗi ô vuông có giá trị 1 hoặc 2. bảng ô vuông có thể dịch chuyển theo một trong bốn cách Up-Down-Left-Right:
- Up: các dòng dịch chuyển lên trên 1 dòng, dòng trên cùng dịch chuyển xuống dưới cùng.
- Down: các dòng dịch chuyển xuống dưới 1 dòng, dòng dưới cùng dịch chuyển lên trên cùng
- Left : các cột dịch chuyển sang trái 1 cột, cột tráu nhất dịch chuyển tới cột phải nhất.
- Right : các cột dịch chuyển sang phải 1 cột, cột phải nhất dịch chuyển tới cột trái nhất.
Cho T truy vấn thuộc một trong 4 loại:
- 1 x : thực hiện x lệnh Down với bảng ô vuông đã cho.
- 2 x : thực hiện x lệnh Right với bảng ô vuông đã cho.
- 4 x : thực hiện x lệnh Left với bảng ô vuông đã cho.
Với mỗi truy vấn hãy đưa ra số ô vuông 2x2 có tổng bằng 4 hoặc 8.
Input
Dòng đầu tiên là số testcase T của bài toán
Dòng đầu tiên của mỗi testcase là 3 số N, M, K. Lần lượt là số dòng, số cột của ma trận và số truy vấn
N dòng tiếp theoi, mỗi dòng chứa M số (1, 2) cho biết giá trị tại vị trí (i, j)
K dòng tiếp theo, mỗi dòng là một truy vấn theo định dạng trên.
Output
Mỗi tescase được in trên 1 dòng, với băt đầu là ký tự '#', tiếp theo là số thứ tự của testcase, tiếp đến là 1 khoảng trắng (dấu cách), và cuối cùng là K kết quả của từng truy vấn (mỗi kết quả cách nhau bởi 1 dấu cách)
Giới hạn
1 <= T <= 70
3 <= N, M <= 2000
1<= K <= 10^5
1 <= x <= 10^9
Example
Input: 1
4 5 5
1 1 2 2 2
1 1 2 2 2
2 2 2 2 1
1 1 1 1 1
1 1
1 2
1 3
2 1
2 2 Output: #1 5 4 2 3 2
Added by: | Đặng Xuân Bảo |
Date: | 2020-03-31 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |