Longest Zigzag Path in a Grid

Problem: Longest Zigzag Path in a Grid You are given an m x n integer grid grid. You may start from any cell. In one move, you may move to one of the four adjacent cells: up, down, left, or right. A valid path must be a strict zigzag path. The comparison directions between consecutive values must alternate, so the values along the path must match one of the following patterns: grid[p0] < grid[p1] > grid[p2] < grid[p3] > ... or: grid[p0] > grid[p1] < grid[p2] > grid[p3] < ... In other words, if the previous move is increasing, the next move must be decreasing; if the previous move is decreasing, the next move must be increasing. If two adjacent cells have equal values, they cannot form an increasing or decreasing step, so that move is invalid. To avoid infinite loops, a path cannot visit the same cell more than once. Return the length of the longest valid zigzag path. The length is the number of cells in the path. Input Format m n grid[0][0] grid[0][1] ... grid[0][n-1] ... grid[m-1][0] grid[m-1][1] ... grid[m-1][n-1] Output Format length of the longest zigzag path Constraints 1 <= m, n <= 8 -10^9 <= grid[i][j] <= 10^9 A path cannot visit the same cell more than once. Example Input: 2 3 1 3 2 4 1 5 Output: 5 Explanation: One longest path is 4 -> 1 -> 5 -> 2 -> 3, with comparison directions down, up, down, up. Example Input 1 1 5 Output 1