You are given a 2D array grid of size m x n, and an integer k. There are k cells in grid containing the values from 1 to k exactly once, and the rest of the cells have a value 0.
You can start at any cell, and move from a cell to its neighbors (up, down, left, or right). You must find a path in grid which:
grid exactly once.k in order.Return a 2D array result of size (m * n) x 2, where result[i] = [xi, yi] represents the ith cell visited in the path. If there are multiple such paths, you may return any one.
If no such path exists, return an empty array.
Example 1:
Input: grid = [[0,0,0],[0,1,2]], k = 2
Output: [[0,0],[1,0],[1,1],[1,2],[0,2],[0,1]]
Explanation:
Example 2:
Input: grid = [[1,0,4],[3,0,2]], k = 4
Output: []
Explanation:
There is no possible path that satisfies the conditions.
Constraints:
1 <= m == grid.length <= 51 <= n == grid[i].length <= 51 <= k <= m * n0 <= grid[i][j] <= kgrid contains all integers between 1 and k exactly once.Note that the matrix size does not exceed 6 times 6, so we can use state compression to represent the visited cells. We can use an integer st to represent the visited cells, where the i-th bit being 1 means cell i has been visited, and 0 means it has not been visited.
Next, we iterate through each cell as a starting point. If the cell is 0 or 1, we start a depth-first search (DFS) from that cell. In the DFS, we add the current cell to the path and mark it as visited. Then, we check the value of the current cell. If it equals v, we increment v by 1. Next, we try to move in four directions to adjacent cells. If the adjacent cell has not been visited and its value is 0 or v, we continue the DFS.
If the DFS successfully finds a complete path, we return that path. If a complete path cannot be found, we backtrack, undo the visit mark for the current cell, and try other directions.
The time complexity is O(m^2 times n^2), and the space complexity is O(m times n), where m and n are the number of rows and columns of the matrix, respectively.
Java
C++
Go
TypeScript
Practice Sequential Grid Path Cover with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor