#P9698. [GDCPC 2023] Path Planning
[GDCPC 2023] Path Planning
题目描述
There is a grid with rows and columns. Each cell of the grid has an integer in it, where indicates the integer in the cell located at the -th row and the -th column. Each integer from to (both inclusive) appears exactly once in the grid.
Let be the cell located at the -th row and the -th column. You now start from and need to reach . When you are in cell , you can either move to its right cell if or move to its bottom cell if .
Let be the set consisting of integers in each cell on your path, including and . Let be the smallest non-negative integer which does not belong to . Find a path to maximize and calculate this maximum possible value.
输入格式
There are multiple test cases. The first line of the input contains an integer indicating the number of test cases. For each test case:
The first line contains two integers and (, ) indicating the number of rows and columns of the grid.
For the following lines, the -th line contains integers () where indicates the integer in cell . Each integer from to (both inclusive) appears exactly once in the grid.
It's guaranteed that the sum of of all test cases will not exceed .
输出格式
For each test case output one line containing one integer indicating the maximum possible value of .
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 possible paths.
- The first path is . so .
- The second path is . so .
- The third path is . so .
So the answer is .
For the second sample test case there is only possible path, which is . so .