#P9698. [GDCPC 2023] Path Planning

[GDCPC 2023] Path Planning

题目描述

There is a grid with nn rows and mm columns. Each cell of the grid has an integer in it, where ai,ja_{i, j} indicates the integer in the cell located at the ii-th row and the jj-th column. Each integer from 00 to (n×m1)(n \times m - 1) (both inclusive) appears exactly once in the grid.

Let (i,j)(i, j) be the cell located at the ii-th row and the jj-th column. You now start from (1,1)(1, 1) and need to reach (n,m)(n, m). When you are in cell (i,j)(i, j), you can either move to its right cell (i,j+1)(i, j + 1) if j<mj < m or move to its bottom cell (i+1,j)(i + 1, j) if i<ni < n.

Let S\mathbb{S} be the set consisting of integers in each cell on your path, including a1,1a_{1, 1} and an,ma_{n, m}. Let mex(S)\text{mex}(\mathbb{S}) be the smallest non-negative integer which does not belong to S\mathbb{S}. Find a path to maximize mex(S)\text{mex}(\mathbb{S}) and calculate this maximum possible value.

输入格式

There are multiple test cases. The first line of the input contains an integer TT indicating the number of test cases. For each test case:

The first line contains two integers nn and mm (1n,m1061 \le n, m \le 10^6, 1n×m1061 \le n \times m \le 10^6) indicating the number of rows and columns of the grid.

For the following nn lines, the ii-th line contains mm integers ai,1,ai,2,,ai,ma_{i, 1}, a_{i, 2}, \cdots, a_{i, m} (0ai,j<n×m0 \le a_{i, j} < n \times m) where ai,ja_{i, j} indicates the integer in cell (i,j)(i, j). Each integer from 00 to (n×m1)(n \times m - 1) (both inclusive) appears exactly once in the grid.

It's guaranteed that the sum of n×mn \times m of all test cases will not exceed 10610^6.

输出格式

For each test case output one line containing one integer indicating the maximum possible value of mex(S)\text{mex}(\mathbb{S}).

2
2 3
1 2 4
3 0 5
1 5
1 3 0 4 2
3
5

提示

For the first sample test case there are 33 possible paths.

  • The first path is (1,1)(1,2)(1,3)(2,3)(1, 1) \to (1, 2) \to (1, 3) \to (2, 3). S={1,2,4,5}\mathbb{S} = \{1, 2, 4, 5\} so mex(S)=0\text{mex}(\mathbb{S}) = 0.
  • The second path is (1,1)(1,2)(2,2)(2,3)(1, 1) \to (1, 2) \to (2, 2) \to (2, 3). S={1,2,0,5}\mathbb{S} = \{1, 2, 0, 5\} so mex(S)=3\text{mex}(\mathbb{S}) = 3.
  • The third path is (1,1)(2,1)(2,2)(2,3)(1, 1) \to (2, 1) \to (2, 2) \to (2, 3). S={1,3,0,5}\mathbb{S} = \{1, 3, 0, 5\} so mex(S)=2\text{mex}(\mathbb{S}) = 2.

So the answer is 33.

For the second sample test case there is only 11 possible path, which is (1,1)(1,2)(1,3)(1,4)(1,5)(1, 1) \to (1, 2) \to (1, 3) \to (1, 4) \to (1, 5). S={1,3,0,4,2}\mathbb{S} = \{1, 3, 0, 4, 2\} so mex(S)=5\text{mex}(\mathbb{S}) = 5.