Sequential Grid Path Cover
<p>You are given a 2D array <code>grid</code> of size <code>m x n</code>, and an integer <code>k</code>. There are <code>k</code> cells in <code>grid</code> containing the values from 1 to <code>k</code> <strong>exactly once</strong>, and the rest of the cells have a value 0.</p>

<p>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 <code>grid</code> which:</p>

<ul>
	<li>Visits each cell in <code>grid</code> <strong>exactly once</strong>.</li>
	<li>Visits the cells with values from 1 to <code>k</code> <strong>in order</strong>.</li>
</ul>

<p>Return a 2D array <code>result</code> of size <code>(m * n) x 2</code>, where <code>result[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents the <code>i<sup>th</sup></code> cell visited in the path. If there are multiple such paths, you may return <strong>any</strong> one.</p>

<p>If no such path exists, return an <strong>empty</strong> array.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[0,0,0],[0,1,2]], k = 2</span></p>

<p><strong>Output:</strong> <span class="example-io">[[0,0],[1,0],[1,1],[1,2],[0,2],[0,1]]</span></p>

<p><strong>Explanation:</strong></p>

<p><img alt="" src="https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/3500-3599/3565.Sequential%20Grid%20Path%20Cover/images/ezgifcom-animated-gif-maker1.gif" style="width: 200px; height: 160px;" /></p>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">grid = [[1,0,4],[3,0,2]], k = 4</span></p>

<p><strong>Output:</strong> <span class="example-io">[]</span></p>

<p><strong>Explanation:</strong></p>

<p>There is no possible path that satisfies the conditions.</p>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= m == grid.length &lt;= 5</code></li>
	<li><code>1 &lt;= n == grid[i].length &lt;= 5</code></li>
	<li><code>1 &lt;= k &lt;= m * n</code></li>
	<li><code>0 &lt;= grid[i][j] &lt;= k</code></li>
	<li><code>grid</code> contains all integers between 1 and <code>k</code> <strong>exactly</strong> once.</li>
</ul>
Recursion; Array; Matrix
func findPath(grid [][]int, k int) [][]int {
	_ = k
	m := len(grid)
	n := len(grid[0])
	var st uint64
	path := [][]int{}
	dirs := []int{-1, 0, 1, 0, -1}

	f := func(i, j int) int { return i*n + j }

	var dfs func(int, int, int) bool
	dfs = func(i, j, v int) bool {
		path = append(path, []int{i, j})
		if len(path) == m*n {
			return true
		}
		idx := f(i, j)
		st |= 1 << idx
		if grid[i][j] == v {
			v++
		}
		for t := 0; t < 4; t++ {
			a, b := dirs[t], dirs[t+1]
			x, y := i+a, j+b
			if 0 <= x && x < m && 0 <= y && y < n {
				idx2 := f(x, y)
				if (st>>idx2)&1 == 0 && (grid[x][y] == 0 || grid[x][y] == v) {
					if dfs(x, y, v) {
						return true
					}
				}
			}
		}
		path = path[:len(path)-1]
		st ^= 1 << idx
		return false
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			if grid[i][j] == 0 || grid[i][j] == 1 {
				if dfs(i, j, 1) {
					return path
				}
				path = path[:0]
				st = 0
			}
		}
	}
	return [][]int{}
}
