On a 2-dimensional grid, there are 4 types of squares:

1 represents the starting square.  There is exactly one starting square.
2 represents the ending square.  There is exactly one ending square.
0 represents empty squares we can walk over.
-1 represents obstacles that we cannot walk over.

Return the number of 4-directional walks from the starting square to the ending square, that walk over every non-obstacle square exactly once.
 

Example 1:
Input: [[1,0,0,0],[0,0,0,0],[0,0,2,-1]]
Output: 2
Explanation: We have the following two paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2)
2. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2)

Example 2:
Input: [[1,0,0,0],[0,0,0,0],[0,0,0,2]]
Output: 4
Explanation: We have the following four paths: 
1. (0,0),(0,1),(0,2),(0,3),(1,3),(1,2),(1,1),(1,0),(2,0),(2,1),(2,2),(2,3)
2. (0,0),(0,1),(1,1),(1,0),(2,0),(2,1),(2,2),(1,2),(0,2),(0,3),(1,3),(2,3)
3. (0,0),(1,0),(2,0),(2,1),(2,2),(1,2),(1,1),(0,1),(0,2),(0,3),(1,3),(2,3)
4. (0,0),(1,0),(2,0),(2,1),(1,1),(0,1),(0,2),(0,3),(1,3),(1,2),(2,2),(2,3)

Example 3:
Input: [[0,1],[2,0]]
Output: 0
Explanation: 
There is no path that walks over every empty square exactly once.
Note that the starting and ending square can be anywhere in the grid.




 
Note:

1 <= grid.length * grid[0].length <= 20

Difficulty: MEDIUM
Tags: Matrices

Bit manipulation

Data structures

Complete search
Skill types: Bit manipulation

Data structures

Complete search

Starter code:
class Solution:
    def uniquePathsIII(self, grid: List[List[int]]) -> int:
        

Solutions:
class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:

		def fun(g, i0, i1, n1, t1, f2, row, col):
			if n1 == t1:
				if abs(f2[1] - i1) + abs(f2[0] - i0) == 1:
					self.ans += 1
			else:
				if i1 + 1 != col and g[i0][i1 + 1] == 0:
					g[i0][i1 + 1] = 1
					fun(g, i0, i1 + 1, n1 + 1, t1, f2, row, col)
					g[i0][i1 + 1] = 0
				if i1 != 0 and g[i0][i1 - 1] == 0:
					g[i0][i1 - 1] = 1
					fun(g, i0, i1 - 1, n1 + 1, t1, f2, row, col)
					g[i0][i1 - 1] = 0
				if i0 + 1 != row and g[i0 + 1][i1] == 0:
					g[i0 + 1][i1] = 1
					fun(g, i0 + 1, i1, n1 + 1, t1, f2, row, col)
					g[i0 + 1][i1] = 0
				if i0 != 0 and g[i0 - 1][i1] == 0:
					g[i0 - 1][i1] = 1
					fun(g, i0 - 1, i1, n1 + 1, t1, f2, row, col)
					g[i0 - 1][i1] = 0
		self.ans = 0
		(i0, i1, t1) = (0, 0, 0)
		f2 = [0, 0]
		row = len(grid)
		col = len(grid[0])
		for i in range(row):
			for j in range(col):
				if grid[i][j] == 0:
					t1 += 1
				elif grid[i][j] == 1:
					(i0, i1) = (i, j)
				elif grid[i][j] == 2:
					f2 = [i, j]
		fun(grid, i0, i1, 0, t1, f2, row, col)
		return self.ans


class Solution:

	def uniquePathsIII(self, grid):
		maxPath = 2
		neighbors = [None] * (len(grid) * len(grid[0]))
		visited = [False] * (len(grid) * len(grid[0]))
		for x in range(len(grid)):
			for y in range(len(grid[0])):
				node = x * len(grid[0]) + y
				if grid[x][y] == 0:
					neighbors[node] = getNeighbors(grid, x, y)
					visited[node] = False
					maxPath += 1
				elif grid[x][y] == 1:
					start = node
					neighbors[node] = getNeighbors(grid, x, y)
				elif grid[x][y] == 2:
					end = node
					visited[node] = False
		return count(neighbors, visited, start, maxPath, 1, end)

def getNeighbors(grid, x, y):
	output = []
	if x > 0 and grid[x - 1][y] % 2 == 0:
		output.append((x - 1) * len(grid[0]) + y)
	if x < len(grid) - 1 and grid[x + 1][y] % 2 == 0:
		output.append((x + 1) * len(grid[0]) + y)
	if y > 0 and grid[x][y - 1] % 2 == 0:
		output.append(x * len(grid[0]) + y - 1)
	if y < len(grid[0]) - 1 and grid[x][y + 1] % 2 == 0:
		output.append(x * len(grid[0]) + y + 1)
	return output

def count(neighbors, visited, node, maxPath, pathLength, destination):
	if pathLength == maxPath and node == destination:
		return 1
	elif pathLength == maxPath or node == destination:
		return 0
	visited[node] = True
	sum = 0
	for k in neighbors[node]:
		if not visited[k]:
			sum += count(neighbors, visited, k, maxPath, pathLength + 1, destination)
	visited[node] = False
	return sum


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		count = 0
		visited = set()

		def dfs(i: int, j: int):
			nonlocal count
			nonlocal num_empty
			if grid[i][j] == -1 or (i, j) in visited:
				return
			elif grid[i][j] == 2 and len(visited) == num_empty + 1:
				count += 1
				return
			else:
				visited.add((i, j))
				if i > 0:
					dfs(i - 1, j)
				if j > 0:
					dfs(i, j - 1)
				if i < len(grid) - 1:
					dfs(i + 1, j)
				if j < len(grid[0]) - 1:
					dfs(i, j + 1)
				visited.remove((i, j))
		start_i = start_j = None
		num_empty = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					(start_i, start_j) = (i, j)
				elif grid[i][j] == 0:
					num_empty += 1
		dfs(start_i, start_j)
		return count


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		non_obstacles = 0
		(start_row, start_col) = (0, 0)
		for row in range(0, rows):
			for col in range(0, cols):
				cell = grid[row][col]
				if cell >= 0:
					non_obstacles += 1
				if cell == 1:
					(start_row, start_col) = (row, col)
		path_count = 0

		def backtrack(row, col, remain):
			nonlocal path_count
			if grid[row][col] == 2 and remain == 1:
				path_count += 1
				return
			temp = grid[row][col]
			grid[row][col] = -4
			remain -= 1
			for (ro, co) in [(0, 1), (0, -1), (-1, 0), (1, 0)]:
				(next_row, next_col) = (row + ro, col + co)
				if not (0 <= next_row < rows and 0 <= next_col < cols):
					continue
				if grid[next_row][next_col] < 0:
					continue
				backtrack(next_row, next_col, remain)
			grid[row][col] = temp
		backtrack(start_row, start_col, non_obstacles)
		return path_count


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:

		def traverse(row, col, spacesLeft):
			if spacesLeft == 1 and grid[row][col] == 2:
				self.results += 1
				return
			temp = grid[row][col]
			grid[row][col] = '#'
			spacesLeft -= 1
			for (rowOffset, colOffset) in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
				(nextRow, nextCol) = (row + rowOffset, col + colOffset)
				if nextRow < 0 or nextRow == rows or nextCol < 0 or (nextCol == cols):
					continue
				if grid[nextRow][nextCol] == -1 or grid[nextRow][nextCol] == '#':
					continue
				traverse(nextRow, nextCol, spacesLeft)
			grid[row][col] = temp
		(rows, cols) = (len(grid), len(grid[0]))
		spaces = 0
		for row in range(rows):
			for col in range(cols):
				if grid[row][col] >= 0:
					spaces += 1
				if grid[row][col] == 1:
					start = (row, col)
		self.results = 0
		traverse(start[0], start[1], spaces)
		return self.results


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:

		def dfs(i, j, out, to_visit):
			if i < 0 or j < 0 or i >= len(grid) or (j >= len(grid[0])) or (grid[i][j] == '#') or (grid[i][j] == -1):
				return
			if grid[i][j] == 2 and to_visit == 0:
				out[0] += 1
			else:
				tmp = grid[i][j]
				grid[i][j] = '#'
				dfs(i, j + 1, out, to_visit - 1)
				dfs(i, j - 1, out, to_visit - 1)
				dfs(i + 1, j, out, to_visit - 1)
				dfs(i - 1, j, out, to_visit - 1)
				grid[i][j] = tmp
		res = [0]
		(ori, orj) = (0, 0)
		to_visit = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					(ori, orj) = (i, j)
				if grid[i][j] != -1:
					to_visit += 1
		dfs(ori, orj, res, to_visit - 1)
		return res[0]


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		start = end = None
		remain = 0
		for m in range(len(grid)):
			for n in range(len(grid[0])):
				if grid[m][n] == 1:
					start = (m, n)
				elif grid[m][n] == 2:
					end = (m, n)
				if grid[m][n] == 0:
					remain += 1
		if start is None or end is None:
			return 0
		return self._helper(grid, start[0], start[1], end[0], end[1], remain + 1)

	def _helper(self, grid: List[List[int]], start_m: int, start_n: int, end_m: int, end_n: int, remain: int) -> int:
		if 0 <= start_m < len(grid) and 0 <= start_n < len(grid[0]) and (grid[start_m][start_n] > -1):
			if remain < 0:
				return 0
			elif remain == 0 and start_m == end_m and (start_n == end_n):
				return 1
			count = 0
			grid[start_m][start_n] = -2
			count += self._helper(grid, start_m + 1, start_n, end_m, end_n, remain - 1)
			count += self._helper(grid, start_m, start_n + 1, end_m, end_n, remain - 1)
			count += self._helper(grid, start_m - 1, start_n, end_m, end_n, remain - 1)
			count += self._helper(grid, start_m, start_n - 1, end_m, end_n, remain - 1)
			grid[start_m][start_n] = 0
			return count
		return 0


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		start = end = None
		cnt = ans = 0
		(m, n) = (len(grid), len(grid[0]))
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					start = (i, j)
				elif grid[i][j] == 1:
					end = (i, j)
				if grid[i][j] != -1:
					cnt += 1

		def dfs(i, j, cnt):
			nonlocal m, n, ans
			if grid[i][j] == 2 and cnt == 1:
				ans += 1
				return
			val = grid[i][j]
			grid[i][j] = -1
			for (x, y) in map(lambda t: (t[0] + i, t[1] + j), [(-1, 0), (1, 0), (0, -1), (0, 1)]):
				if 0 <= x < m and 0 <= y < n and (grid[x][y] != -1):
					dfs(x, y, cnt - 1)
			grid[i][j] = val
		dfs(*start, cnt)
		return ans


from collections import deque

class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		row = len(grid)
		col = len(grid[0])
		r = c = -1
		count = 0
		node_count = 0
		ans = []
		for x in range(row):
			for y in range(col):
				if grid[x][y] >= 0:
					node_count += 1
				if grid[x][y] == 1:
					(r, c) = (x, y)

		def get_paths(sr, sc, remain):
			left = sc - 1
			right = sc + 1
			up = sr - 1
			down = sr + 1
			nonlocal count
			if left >= 0 and grid[sr][left] == 0:
				grid[sr][left] = -4
				get_paths(sr, left, remain - 1)
				grid[sr][left] = 0
			if right < col and grid[sr][right] == 0:
				grid[sr][right] = -4
				get_paths(sr, right, remain - 1)
				grid[sr][right] = 0
			if up >= 0 and grid[up][sc] == 0:
				grid[up][sc] = -4
				get_paths(up, sc, remain - 1)
				grid[up][sc] = 0
			if down < row and grid[down][sc] == 0:
				grid[down][sc] = -4
				get_paths(down, sc, remain - 1)
				grid[down][sc] = 0
			if left >= 0 and grid[sr][left] == 2 and (remain == 2):
				count += 1
			elif right < col and grid[sr][right] == 2 and (remain == 2):
				count += 1
			elif up >= 0 and grid[up][sc] == 2 and (remain == 2):
				count += 1
			elif down < row and grid[down][sc] == 2 and (remain == 2):
				count += 1
		get_paths(r, c, node_count)
		return count


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		self.ret = 0
		empty = 0
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					sx = i
					sy = j
				if grid[i][j] >= 0:
					empty += 1

		def backtrack(grid, x, y, num_left):
			if x < 0 or y < 0 or x >= m or (y >= n) or (grid[x][y] < 0):
				return
			if grid[x][y] == 2 and num_left == 0:
				self.ret += 1
				return
			neighs = [[0, 1], [1, 0], [0, -1], [-1, 0]]
			for (dx, dy) in neighs:
				orig_value = grid[x][y]
				grid[x][y] = -1
				backtrack(grid, x + dx, y + dy, num_left - 1)
				grid[x][y] = orig_value
		backtrack(grid, sx, sy, empty - 1)
		return self.ret


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		(self.ans, empty) = (0, 0)
		(m, n) = (len(grid[0]), len(grid))

		def dfs(x, y, rest):
			if x < 0 or x >= n or y < 0 or (y >= m) or (grid[x][y] < 0):
				return
			if grid[x][y] == 2 and rest == 0:
				self.ans += 1
				return
			neibs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
			for (dx, dy) in neibs:
				tmp = grid[x][y]
				grid[x][y] = -2
				dfs(x + dx, y + dy, rest - 1)
				grid[x][y] = tmp
		for (i, j) in product(list(range(n)), list(range(m))):
			if grid[i][j] == 1:
				(sx, sy) = (i, j)
			empty += grid[i][j] != -1
		dfs(sx, sy, empty - 1)
		return self.ans


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		(rows, cols) = (len(grid), len(grid[0]))
		directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]
		(start_cell, end_cell) = (None, None)
		empty_cells = {}
		for i in range(rows):
			for j in range(cols):
				if grid[i][j] in [0, 1]:
					empty_cells[i, j] = set()
					if grid[i][j] == 1:
						start_cell = (i, j)
				elif grid[i][j] == 2:
					end_cell = (i, j)
		for (x, y) in empty_cells:
			for (xch, ych) in directions:
				neighbor = (x + xch, y + ych)
				if neighbor in empty_cells:
					empty_cells[x, y].add(neighbor)
		next_to_finish = set(((end_cell[0] + xch, end_cell[1] + ych) for (xch, ych) in directions))
		visited = set([start_cell])

		def count_routes(cell=start_cell):
			left_to_visit = len(empty_cells) - len(visited)
			if not left_to_visit:
				return int(cell in next_to_finish)
			routes_to_end = 0
			for neighbor in empty_cells[cell] - visited:
				visited.add(neighbor)
				routes_to_end += count_routes(neighbor)
				visited.remove(neighbor)
			return routes_to_end
		return count_routes()


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:

		def dfs(r, c, n):
			if r < 0 or r >= R or c < 0 or (c >= C) or (grid[r][c] == -1):
				return 0
			if grid[r][c] == 2:
				return n == 0
			grid[r][c] = -1
			paths = dfs(r + 1, c, n - 1) + dfs(r - 1, c, n - 1) + dfs(r, c + 1, n - 1) + dfs(r, c - 1, n - 1)
			grid[r][c] = 0
			return paths
		R = len(grid)
		C = len(grid[0])
		n = 1
		(sr, sc) = (-1, -1)
		for r in range(R):
			for c in range(C):
				if grid[r][c] == 0:
					n += 1
				elif grid[r][c] == 1:
					(sr, sc) = (r, c)
		return dfs(sr, sc, n)


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		self.ans = 0
		(m, n) = (len(grid), len(grid[0]))
		candidates = set()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					(si, sj) = (i, j)
				elif grid[i][j] == 0 or grid[i][j] == 2:
					candidates.add((i, j))

		def helper(i, j):
			if grid[i][j] == 2:
				if not candidates:
					self.ans += 1
				return
			if grid[i][j] == -1:
				return
			if i < m - 1 and (i + 1, j) in candidates:
				candidates.remove((i + 1, j))
				helper(i + 1, j)
				candidates.add((i + 1, j))
			if i > 0 and (i - 1, j) in candidates:
				candidates.remove((i - 1, j))
				helper(i - 1, j)
				candidates.add((i - 1, j))
			if j < n - 1 and (i, j + 1) in candidates:
				candidates.remove((i, j + 1))
				helper(i, j + 1)
				candidates.add((i, j + 1))
			if j > 0 and (i, j - 1) in candidates:
				candidates.remove((i, j - 1))
				helper(i, j - 1)
				candidates.add((i, j - 1))
		helper(si, sj)
		return self.ans


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		(self.ans, self.count) = (0, 0)

		def go(cur, seen):
			(i, j) = cur
			if grid[i][j] == 2:
				if len(seen) == self.count:
					self.ans += 1
				else:
					return
			for (r, c) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
				if 0 <= r < len(grid) and 0 <= c < len(grid[0]) and ((r, c) not in seen) and (grid[r][c] != -1):
					seen.add((r, c))
					go((r, c), seen)
					seen.remove((r, c))
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] in [0, 1, 2]:
					self.count += 1
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == 1:
					go((i, j), {(i, j)})
					return self.ans
		return ans


class Solution:

	def uniquePathsIII(self, A: List[List[int]]) -> int:
		self.res = 0
		rows = len(A)
		cols = len(A[0])
		empty = 1
		for i in range(rows):
			for j in range(cols):
				if A[i][j] == 1:
					(x, y) = (i, j)
				elif A[i][j] == 2:
					end = (i, j)
				elif A[i][j] == 0:
					empty += 1
		self.dfs(A, x, y, empty, end)
		return self.res

	def dfs(self, A, x, y, empty, end):
		if x < 0 or x >= len(A) or y < 0 or (y >= len(A[0])) or (A[x][y] < 0):
			return
		if (x, y) == end:
			self.res += empty == 0
			return
		A[x][y] = -2
		self.dfs(A, x + 1, y, empty - 1, end)
		self.dfs(A, x - 1, y, empty - 1, end)
		self.dfs(A, x, y + 1, empty - 1, end)
		self.dfs(A, x, y - 1, empty - 1, end)
		A[x][y] = 0


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:

		def dfs(i, j, N):
			if N == -1 and grid[i][j] == 2:
				return 1
			grid[i][j] = -1
			res = sum([dfs(row, col, N - 1) for (x, y) in dirs for (row, col) in [(i + x, j + y)] if 0 <= row < m and 0 <= col < n and (N > 0 and (not grid[row][col]) or (N == 0 and grid[row][col] == 2))])
			grid[i][j] = 0
			return res
		(m, n) = (len(grid), len(grid[0]))
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		N = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == 1:
					start = [i, j]
				elif not grid[i][j]:
					N += 1
		return dfs(start[0], start[1], N)


class Solution:

	def uniquePathsIII(self, grid: List[List[int]]) -> int:
		nr = len(grid)
		nc = len(grid[0])
		all_cells = 0
		start = (0, 0)
		res = 0
		direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		for r in range(nr):
			for c in range(nc):
				if grid[r][c] >= 0:
					all_cells += 1
				if grid[r][c] == 1:
					start = (r, c)

		def dfs(r, c, cell_nums):
			nonlocal res
			nonlocal direction
			nonlocal grid
			nonlocal nr
			nonlocal nc
			if grid[r][c] == 2 and cell_nums == 1:
				res += 1
				return
			temp = grid[r][c]
			grid[r][c] = -2
			cell_nums -= 1
			for d in direction:
				rr = r + d[0]
				cc = c + d[1]
				if 0 <= rr < nr and 0 <= cc < nc and (grid[rr][cc] >= 0):
					dfs(rr, cc, cell_nums)
			grid[r][c] = temp
		dfs(*start, all_cells)
		return res