5370: Lawn of the Dead
内存限制：256 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：5
解决：2
题目描述
One day, a zombie came to the Lawn of the Dead, which can be seen as an n×m grid. Initially, he stood on the top-left cell, which is (1,1).
Because the brain of the zombie was broken, he didn't have a good sense of direction. He could only move down from (i,j) to (i+1,j) or right from (i,j) to (i,j+1) in one step.
There were k "lotato mines" on the grid. The i-th mine was at (xi,yi). In case of being destroyed, he would never step into a cell containing a "lotato mine".
So how many cells could he possibly reach? (Including the starting cell)
Because the brain of the zombie was broken, he didn't have a good sense of direction. He could only move down from (i,j) to (i+1,j) or right from (i,j) to (i,j+1) in one step.
There were k "lotato mines" on the grid. The i-th mine was at (xi,yi). In case of being destroyed, he would never step into a cell containing a "lotato mine".
So how many cells could he possibly reach? (Including the starting cell)
输入
The first line contains a single integer t (1≤t≤20), denoting the number of test cases.
The first line of each test case contains three integers n,m,k (2≤n,m,k≤105) --- there was an n×m grid, and there were k "lotato mines" on the grid.
Each of the following k lines contains 2 integers xi,yi (1≤xi≤n,1≤yi≤m) --- there was a "lotato mine" at (xi,yi). It's guaranteed that there was no "lotato mine" at (1,1) and no mines were in the same cell.
It is guaranteed that ∑n≤7⋅105,∑m≤7⋅105.
The first line of each test case contains three integers n,m,k (2≤n,m,k≤105) --- there was an n×m grid, and there were k "lotato mines" on the grid.
Each of the following k lines contains 2 integers xi,yi (1≤xi≤n,1≤yi≤m) --- there was a "lotato mine" at (xi,yi). It's guaranteed that there was no "lotato mine" at (1,1) and no mines were in the same cell.
It is guaranteed that ∑n≤7⋅105,∑m≤7⋅105.
输出
For each test case, output the number of cells he could possibly reach.
样例输入 复制
1
4 4 4
1 3
3 4
3 2
4 3样例输出 复制
10提示
The cells that the zombie might reach are (1,1), (1,2), (2,1), (2,2), (2,3), (2,4), (3,1), (3,3), (4,1), (4,2).