← 返回 google 的题目列表Longest Non-Increasing Path in Grid with One-Step Lookback Constraint
类型：online_judge
Given an m x n integer matrix grid, you may start from any cell and build a path. Each step can move only to one of the 4-directionally adjacent cells (up/down/left/right).
Let three consecutive cells on the path be A -> B -> C (where A is the previous cell, B is the current cell, and C is the next cell). The move constraints are:
The first move A -> B must satisfy value(B) <= value(A).
For every subsequent move B -> C, it must satisfy: value(C) <= value(B) or value(C) <= value(A) (i.e., the next value is no greater than the current value, or no greater than the value one step back).
Return the maximum possible path length (number of visited cells) under these rules.
Input format (suggested)
First line: m n
Next m lines: n integers each
Output format (suggested)
One integer: the maximum path length
Constraints (for self-testing)
1 <= m,n <= 200
-1e9 <= grid[i][j] <= 1e9
Sample tests 1.
1 1
7
Output:
1
2 2
4 3
2 1
Output:
4
2 3
3 3 3
3 3 3
Output:
6
3 3
5 4 5
6 1 2
7 8 0
Output:
3
2 2
1 100
100 1
Output:
2
Example
Input
1 1
7
Output
1