In an n*n grid, there is a snake that spans 2 cells and starts moving from the top left corner at (0, 0) and (0, 1). The grid has empty cells represented by zeros and blocked cells represented by ones. The snake wants to reach the lower right corner at (n-1, n-2) and (n-1, n-1).
In one move the snake can:

Move one cell to the right if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Move down one cell if there are no blocked cells there. This move keeps the horizontal/vertical position of the snake as it is.
Rotate clockwise if it's in a horizontal position and the two cells under it are both empty. In that case the snake moves from (r, c) and (r, c+1) to (r, c) and (r+1, c).

Rotate counterclockwise if it's in a vertical position and the two cells to its right are both empty. In that case the snake moves from (r, c) and (r+1, c) to (r, c) and (r, c+1).


Return the minimum number of moves to reach the target.
If there is no way to reach the target, return -1.
 
Example 1:

Input: grid = [[0,0,0,0,0,1],
               [1,1,0,0,1,0],
               [0,0,0,0,1,1],
               [0,0,1,0,1,0],
               [0,1,1,0,0,0],
               [0,1,1,0,0,0]]
Output: 11
Explanation:
One possible solution is [right, right, rotate clockwise, right, down, down, down, down, rotate counterclockwise, right, down].

Example 2:
Input: grid = [[0,0,1,1,1,1],
               [0,0,0,0,1,1],
               [1,1,0,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,1],
               [1,1,1,0,0,0]]
Output: 9

 
Constraints:

2 <= n <= 100
0 <= grid[i][j] <= 1
It is guaranteed that the snake starts at empty cells.

Difficulty: MEDIUM
Tags: Matrices

Data structures

Graph traversal
Skill types: Data structures

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

Solutions:
class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		queue = deque([(0, 0, True)])
		dists = {(0, 0, True): 0}
		while queue:
			(i, j, hor) = queue.popleft()
			if (i, j) == (m - 1, n - 2):
				return dists[i, j, hor]
			if hor:
				if j + 2 < n and (not grid[i][j + 2]):
					if (i, j + 1, hor) not in dists:
						queue.append((i, j + 1, hor))
						dists[i, j + 1, hor] = dists[i, j, hor] + 1
				if i + 1 < m and (not grid[i + 1][j]) and (not grid[i + 1][j + 1]):
					if (i + 1, j, hor) not in dists:
						queue.append((i + 1, j, hor))
						dists[i + 1, j, hor] = dists[i, j, hor] + 1
					if (i, j, not hor) not in dists:
						queue.append((i, j, not hor))
						dists[i, j, not hor] = dists[i, j, hor] + 1
			else:
				if i + 2 < m and (not grid[i + 2][j]):
					if (i + 1, j, hor) not in dists:
						queue.append((i + 1, j, hor))
						dists[i + 1, j, hor] = dists[i, j, hor] + 1
				if j + 1 < n and (not grid[i][j + 1]) and (not grid[i + 1][j + 1]):
					if (i, j + 1, hor) not in dists:
						queue.append((i, j + 1, hor))
						dists[i, j + 1, hor] = dists[i, j, hor] + 1
					if (i, j, not hor) not in dists:
						queue.append((i, j, not hor))
						dists[i, j, not hor] = dists[i, j, hor] + 1
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		q = collections.deque([(0, 0, 0, 1, 0)])
		visited = set([(0, 0, 0, 1)])
		while q:
			(tailx, taily, headx, heady, steps) = q.popleft()
			if tailx == n - 1 and taily == n - 2 and (headx == n - 1) and (heady == n - 1):
				return steps
			for (n_tailx, n_taily, n_headx, n_heady) in ((tailx, taily + 1, headx, heady + 1), (tailx + 1, taily, headx + 1, heady)):
				if 0 <= n_tailx < n and 0 <= n_taily < n and (0 <= n_headx < n) and (0 <= n_heady < n) and ((n_tailx, n_taily, n_headx, n_heady) not in visited) and (grid[n_headx][n_heady] == 0) and (grid[n_tailx][n_taily] == 0):
					visited.add((n_tailx, n_taily, n_headx, n_heady))
					q.append((n_tailx, n_taily, n_headx, n_heady, steps + 1))
			if tailx == headx:
				if tailx + 1 < n and grid[tailx + 1][taily] == 0 and (grid[headx + 1][heady] == 0) and ((tailx, taily, tailx + 1, taily) not in visited):
					visited.add((tailx, taily, tailx + 1, taily))
					q.append((tailx, taily, tailx + 1, taily, steps + 1))
			if taily == heady:
				if taily + 1 < n and grid[tailx][taily + 1] == 0 and (grid[headx][heady + 1] == 0) and ((tailx, taily, tailx, taily + 1) not in visited):
					visited.add((tailx, taily, tailx, taily + 1))
					q.append((tailx, taily, tailx, taily + 1, steps + 1))
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		start = (0, 0, 0, 1)
		end = (n - 1, n - 2, n - 1, n - 1)
		curr_level = {start}
		moves = 0
		visited = set()
		while curr_level:
			next_level = set()
			for pos in curr_level:
				visited.add(pos)
				(r1, c1, r2, c2) = pos
				if c1 + 1 < n and grid[r1][c1 + 1] == 0 and (c2 + 1 < n) and (grid[r2][c2 + 1] == 0):
					if (r1, c1 + 1, r2, c2 + 1) not in visited:
						next_level.add((r1, c1 + 1, r2, c2 + 1))
				if r1 + 1 < n and grid[r1 + 1][c1] == 0 and (r2 + 1 < n) and (grid[r2 + 1][c2] == 0):
					if (r1 + 1, c1, r2 + 1, c1) not in visited:
						next_level.add((r1 + 1, c1, r2 + 1, c2))
				if r1 == r2 and c2 == c1 + 1 and (r1 + 1 < n) and (grid[r1 + 1][c1] + grid[r1 + 1][c1 + 1] == 0):
					if (r1, c1, r1 + 1, c1) not in visited:
						next_level.add((r1, c1, r1 + 1, c1))
				if c1 == c2 and r2 == r1 + 1 and (c1 + 1 < n) and (grid[r1][c1 + 1] + grid[r1 + 1][c1 + 1] == 0):
					if (r1, c1, r1, c1 + 1) not in visited:
						next_level.add((r1, c1, r1, c1 + 1))
			if end in next_level:
				return moves + 1
			curr_level = next_level
			moves += 1
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		q = [((0, 1), (0, 0))]
		visited = set(q)
		step = 0
		while q:
			l = len(q)
			for _ in range(l):
				(head, tail) = q.pop(0)
				if head == (n - 1, n - 1) and tail == (n - 1, n - 2):
					return step
				if head[1] > tail[1]:
					if head[1] + 1 < n and grid[head[0]][head[1] + 1] == 0 and (not ((head[0], head[1] + 1), (tail[0], tail[1] + 1)) in visited):
						q.append(((head[0], head[1] + 1), (tail[0], tail[1] + 1)))
						visited.add(((head[0], head[1] + 1), (tail[0], tail[1] + 1)))
					if head[0] + 1 < n and grid[head[0] + 1][head[1]] + grid[tail[0] + 1][tail[1]] == 0:
						if not ((head[0] + 1, head[1]), (tail[0] + 1, tail[1])) in visited:
							q.append(((head[0] + 1, head[1]), (tail[0] + 1, tail[1])))
							visited.add(((head[0] + 1, head[1]), (tail[0] + 1, tail[1])))
						if not ((head[0] + 1, head[1] - 1), tail) in visited:
							q.append(((head[0] + 1, head[1] - 1), tail))
							visited.add(((head[0] + 1, head[1] - 1), tail))
				else:
					if head[0] + 1 < n and grid[head[0] + 1][head[1]] == 0 and (not ((head[0] + 1, head[1]), (tail[0] + 1, tail[1])) in visited):
						q.append(((head[0] + 1, head[1]), (tail[0] + 1, tail[1])))
						visited.add(((head[0] + 1, head[1]), (tail[0] + 1, tail[1])))
					if head[1] + 1 < n and grid[head[0]][head[1] + 1] + grid[tail[0]][tail[1] + 1] == 0:
						if not ((head[0], head[1] + 1), (tail[0], tail[1] + 1)) in visited:
							q.append(((head[0], head[1] + 1), (tail[0], tail[1] + 1)))
							visited.add(((head[0], head[1] + 1), (tail[0], tail[1] + 1)))
						if not ((head[0] - 1, head[1] + 1), tail) in visited:
							q.append(((head[0] - 1, head[1] + 1), tail))
							visited.add(((head[0] - 1, head[1] + 1), tail))
			step += 1
		return -1


from collections import deque

class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		visited = {(0, 1, 0, 0)}
		moves = -1
		queue = deque([(0, 1, 0, 0)])
		while queue:
			level_len = len(queue)
			moves += 1
			for _ in range(level_len):
				tp = queue.popleft()
				(curr, last) = (tp[:2], tp[2:])
				if tp == (n - 1, n - 1, n - 1, n - 2):
					return moves
				if curr[1] + 1 < n and last[1] + 1 < n and (grid[curr[0]][curr[1] + 1] == 0) and (grid[last[0]][last[1] + 1] == 0) and ((curr[0], curr[1] + 1, last[0], last[1] + 1) not in visited):
					visited.add((curr[0], curr[1] + 1, last[0], last[1] + 1))
					queue.append((curr[0], curr[1] + 1, last[0], last[1] + 1))
				if curr[0] + 1 < n and last[0] + 1 < n and (grid[curr[0] + 1][curr[1]] == 0) and (grid[last[0] + 1][last[1]] == 0) and ((curr[0] + 1, curr[1], last[0] + 1, last[1]) not in visited):
					visited.add((curr[0] + 1, curr[1], last[0] + 1, last[1]))
					queue.append((curr[0] + 1, curr[1], last[0] + 1, last[1]))
				if curr[0] == last[0] and curr[0] + 1 < n and (grid[curr[0] + 1][curr[1]] == 0) and (grid[last[0] + 1][last[1]] == 0) and ((curr[0] + 1, curr[1] - 1, last[0], last[1]) not in visited):
					visited.add((curr[0] + 1, curr[1] - 1, last[0], last[1]))
					queue.append((curr[0] + 1, curr[1] - 1, last[0], last[1]))
				if curr[1] == last[1] and curr[1] + 1 < n and (grid[curr[0]][curr[1] + 1] == 0) and (grid[last[0]][last[1] + 1] == 0) and ((curr[0] - 1, curr[1] + 1, last[0], last[1]) not in visited):
					visited.add((curr[0] - 1, curr[1] + 1, last[0], last[1]))
					queue.append((curr[0] - 1, curr[1] + 1, last[0], last[1]))
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		visited = set()
		queue = deque()
		n = len(grid)
		queue.append((0, 0, 0, 1))
		visited.add(queue[0])
		res = 0
		target = (n - 1, n - 2, n - 1, n - 1)
		while queue:
			size = len(queue)
			for _ in range(size):
				curr = queue.popleft()
				if curr == target:
					return res
				horizontal = curr[0] == curr[2]
				moves = []
				if curr[3] < n - 1 and grid[curr[0]][curr[1] + 1] == 0 and (grid[curr[2]][curr[3] + 1] == 0):
					moves.append((curr[0], curr[1] + 1, curr[2], curr[3] + 1))
				if curr[2] < n - 1 and grid[curr[0] + 1][curr[1]] == 0 and (grid[curr[2] + 1][curr[3]] == 0):
					moves.append((curr[0] + 1, curr[1], curr[2] + 1, curr[3]))
				if horizontal and curr[2] < n - 1 and (grid[curr[0] + 1][curr[1]] == 0) and (grid[curr[2] + 1][curr[3]] == 0):
					moves.append((curr[0], curr[1], curr[0] + 1, curr[1]))
				if not horizontal and curr[3] < n - 1 and (grid[curr[0]][curr[1] + 1] == 0) and (grid[curr[2]][curr[3] + 1] == 0):
					moves.append((curr[0], curr[1], curr[0], curr[1] + 1))
				for move in moves:
					if move not in visited:
						visited.add(move)
						queue.append(move)
			res += 1
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		stack = [(0, 0, 0, 0, 1)]
		n = len(grid)
		visited = set()
		visited.add((0, 0, 0, 1))
		while stack:
			(stepNow, ia, ja, ib, jb) = heapq.heappop(stack)
			(ia1, ja1, ib1, jb1) = (ia, ja + 1, ib, jb + 1)
			if jb1 < n and grid[ib1][jb1] == 0 and (grid[ia1][ja1] == 0) and ((ia1, ja1, ib1, jb1) not in visited):
				if (ia1, ja1, ib1, jb1) == (n - 1, n - 2, n - 1, n - 1):
					return stepNow + 1
				visited.add((ia1, ja1, ib1, jb1))
				heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1))
			(ia1, ja1, ib1, jb1) = (ia + 1, ja, ib + 1, jb)
			if ia1 < n and ib1 < n and (grid[ib1][jb1] == 0) and (grid[ia1][ja1] == 0) and ((ia1, ja1, ib1, jb1) not in visited):
				if (ia1, ja1, ib1, jb1) == (n - 1, n - 2, n - 1, n - 1):
					return stepNow + 1
				visited.add((ia1, ja1, ib1, jb1))
				heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1))
			if ia == ib and ja == jb - 1:
				if ia + 1 < n and grid[ia + 1][ja] == 0 and (grid[ib + 1][jb] == 0):
					(ia1, ja1, ib1, jb1) = (ia, ja, ia + 1, ja)
					if (ia1, ja1, ib1, jb1) not in visited:
						if (ia1, ja1, ib1, jb1) == (n - 1, n - 2, n - 1, n - 1):
							return stepNow + 1
						visited.add((ia1, ja1, ib1, jb1))
						heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1))
			if ja == jb and ia == ib - 1:
				if ja + 1 < n and grid[ia][ja + 1] == 0 and (grid[ib][jb + 1] == 0):
					(ia1, ja1, ib1, jb1) = (ia, ja, ia, ja + 1)
					if (ia1, ja1, ib1, jb1) not in visited:
						if (ia1, ja1, ib1, jb1) == (n - 1, n - 2, n - 1, n - 1):
							return stepNow + 1
						visited.add((ia1, ja1, ib1, jb1))
						heapq.heappush(stack, (stepNow + 1, ia1, ja1, ib1, jb1))
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		m = n = len(grid)
		visited = {0}

		@lru_cache(None)
		def move(i, j, k, r):
			if i == m - 1 and j == n - 1 and (k == 0):
				return 0
			result = 1000000000.0
			if k == 0:
				if j + 1 < n and grid[i][j + 1] != 1:
					result = min(result, 1 + move(i, j + 1, k, 0))
				if i + 1 < m and grid[i + 1][j] != 1 and (grid[i + 1][j - 1] != 1):
					result = min(result, 1 + move(i + 1, j, k, 0))
					if not r:
						result = min(result, 1 + move(i + 1, j - 1, 1, 1))
			else:
				if i + 1 < m and grid[i + 1][j] != 1:
					result = min(result, 1 + move(i + 1, j, k, 0))
				if j + 1 < n and grid[i][j + 1] != 1 and (grid[i - 1][j + 1] != 1):
					result = min(result, 1 + move(i, j + 1, k, 0))
					if not r:
						result = min(result, 1 + move(i - 1, j + 1, 0, 1))
			return result
		result = move(0, 1, 0, 0)
		return result if result < 1000000000.0 else -1


class Solution:

	def is_empty(self, xy):
		if 0 <= xy[0] < self.m and 0 <= xy[1] < self.n:
			return self.grid[xy[0]][xy[1]] == 0
		else:
			return False

	def next_positions(self, pos):
		(tail, head) = pos
		if tail[0] == head[0]:
			if self.is_empty((head[0], head[1] + 1)):
				yield (head, (head[0], head[1] + 1))
			if self.is_empty((tail[0] + 1, tail[1])) and self.is_empty((head[0] + 1, head[1])):
				yield ((tail[0] + 1, tail[1]), (head[0] + 1, head[1]))
				yield (tail, (tail[0] + 1, tail[1]))
		else:
			assert tail[1] == head[1]
			if self.is_empty((head[0] + 1, head[1])):
				yield (head, (head[0] + 1, head[1]))
			if self.is_empty((tail[0], tail[1] + 1)) and self.is_empty((head[0], head[1] + 1)):
				yield ((tail[0], tail[1] + 1), (head[0], head[1] + 1))
				yield (tail, (tail[0], tail[1] + 1))

	def minimumMoves(self, grid: List[List[int]]) -> int:
		self.grid = grid
		self.m = len(grid)
		self.n = len(grid[0])
		layer = {((0, 0), (0, 1))}
		visited = set()
		dist = 0
		target = ((self.m - 1, self.n - 2), (self.m - 1, self.n - 1))
		while layer:
			if target in layer:
				return dist
			visited |= layer
			next_layer = set()
			for pos in layer:
				for next_pos in self.next_positions(pos):
					if next_pos not in visited:
						next_layer.add(next_pos)
			layer = next_layer
			dist += 1
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		queue = collections.deque([(0, 0, 0, 1, 0)])
		visited = {(0, 0, 0, 1)}
		while queue:
			(r0, c0, r1, c1, steps) = queue.popleft()
			print(r0, c0, r1, c1, steps)
			if r0 == n - 1 and r1 == n - 1 and (c0 == n - 2) and (c1 == n - 1):
				return steps
			if r0 == r1:
				if 0 <= c1 + 1 < n and (not grid[r1][c1 + 1]) and ((r1, c1, r1, c1 + 1) not in visited):
					visited.add((r1, c1, r1, c1 + 1))
					queue.append((r1, c1, r1, c1 + 1, steps + 1))
				if 0 <= r0 + 1 < n and (not grid[r0 + 1][c0]) and (not grid[r1 + 1][c1]):
					if (r0 + 1, c0, r1 + 1, c1) not in visited:
						visited.add((r0 + 1, c0, r1 + 1, c1))
						queue.append((r0 + 1, c0, r1 + 1, c1, steps + 1))
					if (r0, c0, r0 + 1, c0) not in visited:
						visited.add((r0, c0, r0 + 1, c0))
						queue.append((r0, c0, r0 + 1, c0, steps + 1))
			else:
				if 0 <= c0 + 1 < n and (not grid[r0][c0 + 1]) and (not grid[r1][c1 + 1]):
					if (r0, c0 + 1, r1, c1 + 1) not in visited:
						visited.add((r0, c0 + 1, r1, c1 + 1))
						queue.append((r0, c0 + 1, r1, c1 + 1, steps + 1))
					if (r0, c0, r0, c0 + 1) not in visited:
						visited.add((r0, c0, r0, c0 + 1))
						queue.append((r0, c0, r0, c0 + 1, steps + 1))
				if 0 <= r1 + 1 < n and (not grid[r1 + 1][c1]):
					if (r1, c1, r1 + 1, c1) not in visited:
						visited.add((r1, c1, r1 + 1, c1))
						queue.append((r1, c1, r1 + 1, c1, steps + 1))
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		num_steps_horizontal = [[float('inf') for _ in range(n)] for _ in range(n)]
		num_steps_vertical = [[float('inf') for _ in range(n)] for _ in range(n)]
		if not grid[0][0] == grid[0][1] == 0:
			raise ValueError
		num_steps_horizontal[0][0] = 0
		for col in range(1, n - 1):
			if grid[0][col + 1] == 0:
				num_steps_horizontal[0][col] = 1 + num_steps_horizontal[0][col - 1]
			else:
				break
		for row in range(n):
			for col in range(n):
				if col < n - 1 and grid[row][col] == grid[row][col + 1] == 0:
					num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_horizontal[row][col - 1], 1 + num_steps_horizontal[row - 1][col])
				if row < n - 1 and grid[row][col] == grid[row + 1][col] == 0:
					num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_vertical[row][col - 1], 1 + num_steps_vertical[row - 1][col])
				if col < n - 1 and row < n - 1 and (grid[row][col] == grid[row][col + 1] == 0) and (grid[row + 1][col] == grid[row + 1][col + 1] == 0):
					num_steps_horizontal[row][col] = min(num_steps_horizontal[row][col], 1 + num_steps_vertical[row][col])
					num_steps_vertical[row][col] = min(num_steps_vertical[row][col], 1 + num_steps_horizontal[row][col])
		if num_steps_horizontal[-1][-2] < float('inf'):
			return num_steps_horizontal[-1][-2]
		else:
			return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		(queue, visited, n) = (collections.deque([((0, 0), (0, 1), 0)]), set(), len(grid))
		target = ((n - 1, n - 2), (n - 1, n - 1))
		while queue:
			((r1, c1), (r2, c2), steps) = queue.popleft()
			if ((r1, c1), (r2, c2)) == target:
				return steps
			if ((r1, c1), (r2, c2)) in visited:
				continue
			visited |= {((r1, c1), (r2, c2))}
			if c1 + 1 < n and grid[r1][c1 + 1] == 0 and (c2 + 1 < n) and (grid[r2][c2 + 1] == 0):
				queue.append(((r1, c1 + 1), (r2, c2 + 1), steps + 1))
			if r1 + 1 < n and grid[r1 + 1][c1] == 0 and (r2 + 1 < n) and (grid[r2 + 1][c2] == 0):
				queue.append(((r1 + 1, c1), (r2 + 1, c2), steps + 1))
			if r1 == r2 and r1 + 1 < n and (grid[r1 + 1][c1] + grid[r1 + 1][c1 + 1] == 0):
				queue.append(((r1, c1), (r1 + 1, c1), steps + 1))
			if c1 == c2 and c1 + 1 < n and (grid[r1][c1 + 1] + grid[r1 + 1][c1 + 1] == 0):
				queue.append(((r1, c1), (r1, c1 + 1), steps + 1))
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		dp = [[[float('inf'), float('inf')] for _ in range(n + 1)] for _ in range(n + 1)]
		dp[0][1][0] = dp[1][0][0] = -1
		for r in range(1, n + 1):
			for c in range(1, n + 1):
				(h, v) = (False, False)
				if grid[r - 1][c - 1] == 0 and c < n and (grid[r - 1][c] == 0):
					dp[r][c][0] = min(dp[r - 1][c][0], dp[r][c - 1][0]) + 1
					h = True
				if grid[r - 1][c - 1] == 0 and r < n and (grid[r][c - 1] == 0):
					dp[r][c][1] = min(dp[r - 1][c][1], dp[r][c - 1][1]) + 1
					v = True
				if v and c < n and (grid[r][c] == 0):
					dp[r][c][1] = min(dp[r][c][1], dp[r][c][0] + 1)
				if h and r < n and (grid[r][c] == 0):
					dp[r][c][0] = min(dp[r][c][0], dp[r][c][1] + 1)
		return dp[n][n - 1][0] if dp[n][n - 1][0] < float('inf') else -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		(q, seen, target) = ([(0, 0, 0, 0)], set(), (n - 1, n - 2, 0))
		for (r, c, dr, steps) in q:
			if (r, c, dr) == target:
				return steps
			if (r, c, dr) not in seen:
				seen.add((r, c, dr))
				if dr:
					if c + 1 < n and grid[r][c + 1] + grid[r + 1][c + 1] == 0:
						q += [(r, c + 1, 1, steps + 1), (r, c, 0, steps + 1)]
					if r + 2 < n and grid[r + 2][c] == 0:
						q += [(r + 1, c, 1, steps + 1)]
				else:
					if r + 1 < n and grid[r + 1][c] + grid[r + 1][c + 1] == 0:
						q += [(r + 1, c, 0, steps + 1), (r, c, 1, steps + 1)]
					if c + 2 < n and grid[r][c + 2] == 0:
						q += [(r, c + 1, 0, steps + 1)]
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		vis = set()
		q = collections.deque([(0, 0, 0, 0)])
		d = [[0, 1], [1, 0]]
		n = len(grid)
		while q:
			node = q.popleft()
			if node[0] == n - 1 and node[1] == n - 2 and (node[2] == 0):
				return node[3]
			snake = [[node[0], node[1]], [node[0] + d[node[2]][0], node[1] + d[node[2]][1]]]
			for i in d:
				possible = True
				for c in snake:
					nx = c[0] + i[0]
					ny = c[1] + i[1]
					if nx < 0 or ny < 0 or nx >= n or (ny >= n):
						possible = False
						break
					if grid[nx][ny] != 0:
						possible = False
						break
				if possible:
					nx = node[0] + i[0]
					ny = node[1] + i[1]
					if (nx, ny, node[2]) not in vis:
						vis.add((nx, ny, node[2]))
						q.append((nx, ny, node[2], node[3] + 1))
					if node[2] == 0 and i[0] == 1:
						if (node[0], node[1], 1) not in vis:
							vis.add((node[0], node[1], 1))
							q.append((node[0], node[1], 1, node[3] + 1))
					elif node[2] == 1 and i[0] == 0:
						if (node[0], node[1], 0) not in vis:
							vis.add((node[0], node[1], 0))
							q.append((node[0], node[1], 0, node[3] + 1))
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		q = [(0, 0, 0, 1)]
		moves = 0
		visited = set([(0, 0, 0, 1)])
		while q:
			size = len(q)
			for _ in range(size):
				(x1, y1, x2, y2) = q.pop(0)
				if x1 == n - 1 and y1 == n - 2 and (x2 == n - 1) and (y2 == n - 1):
					return moves
				if y1 + 1 < n and grid[x1][y1 + 1] == 0 and (y2 + 1 < n) and (grid[x2][y2 + 1] == 0):
					if (x1, y1 + 1, x2, y2 + 1) not in visited:
						visited.add((x1, y1 + 1, x2, y2 + 1))
						q.append((x1, y1 + 1, x2, y2 + 1))
				if x1 + 1 < n and grid[x1 + 1][y1] == 0 and (x2 + 1 < n) and (grid[x2 + 1][y2] == 0):
					if (x1 + 1, y1, x2 + 1, y2) not in visited:
						visited.add((x1 + 1, y1, x2 + 1, y2))
						q.append((x1 + 1, y1, x2 + 1, y2))
				if x1 == x2 and y2 == y1 + 1 and (x1 + 1 < n) and (grid[x1 + 1][y1] + grid[x1 + 1][y1 + 1] == 0):
					if (x1, y1, x1 + 1, y1) not in visited:
						visited.add((x1, y1, x1 + 1, y1))
						q.append((x1, y1, x1 + 1, y1))
				if y1 == y2 and x2 == x1 + 1 and (y1 + 1 < n) and (grid[x1][y1 + 1] + grid[x1 + 1][y1 + 1] == 0):
					if (x1, y1, x1, y1 + 1) not in visited:
						visited.add((x1, y1, x1, y1 + 1))
						q.append((x1, y1, x1, y1 + 1))
			moves += 1
		return -1


import heapq
from typing import List

class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		self.grid = grid
		(self.R, self.C) = (len(grid), len(grid[0]))
		target = (self.R - 1, self.C - 1)
		q = [(0, 0, 1, 0)]
		visited = [{(0, 1): 0}, {}]
		while q:
			(d, r, c, o) = heapq.heappop(q)
			(shift_d, shift_r, rot) = (self.shift_down(r, c, o), self.shift_right(r, c, o), self.rotate(r, c, o))
			d += 1
			if shift_d:
				(i, j) = shift_d
				if d < visited[o].get((i, j), float('inf')):
					visited[o][i, j] = d
					heapq.heappush(q, (d, i, j, o))
			if shift_r:
				(i, j) = shift_r
				if d < visited[o].get((i, j), float('inf')):
					visited[o][i, j] = d
					heapq.heappush(q, (d, i, j, o))
			if rot:
				(i, j) = rot
				if d < visited[1 - o].get((i, j), float('inf')):
					visited[1 - o][i, j] = d
					heapq.heappush(q, (d, i, j, 1 - o))
		return visited[0].get(target, -1)

	def shift_right(self, r, c, orient):
		if orient == 0 and (c == self.C - 1 or self.grid[r][c + 1]):
			return False
		if orient == 1 and (c == self.C - 1 or self.grid[r][c + 1] or self.grid[r - 1][c + 1]):
			return False
		return (r, c + 1)

	def shift_down(self, r, c, orient):
		if orient == 1 and (r == self.R - 1 or self.grid[r + 1][c]):
			return False
		if orient == 0 and (r == self.R - 1 or self.grid[r + 1][c] or self.grid[r + 1][c - 1]):
			return False
		return (r + 1, c)

	def rotate(self, r, c, orient):
		if orient == 0 and (r == self.R - 1 or self.grid[r + 1][c] or self.grid[r + 1][c - 1]):
			return False
		if orient == 0:
			return (r + 1, c - 1)
		if c == self.C - 1 or self.grid[r][c + 1] or self.grid[r - 1][c + 1]:
			return False
		return (r - 1, c + 1)


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		(rows, cols) = (len(grid), len(grid[0]))

		def getOr(x1, y1, x2, y2):
			return 'H' if y2 == y1 + 1 else 'V'

		def inB(x, y):
			return x < rows and x >= 0 and (y < cols) and (y >= 0)
		dic = {(rows - 1, cols - 2, rows - 1, cols - 1): 0}

		def dfs(x1, y1, x2, y2, visited):
			mn = float('inf')
			visited.add((x1, y1, x2, y2))
			if x1 == rows - 1 and y1 == cols - 2 and (x2 == rows - 1) and (y2 == cols - 1):
				return 0
			(x, y) = (x1, y1)
			if getOr(x1, y1, x2, y2) == 'H':
				(r1, c1, r2, c2) = (x, y + 1, x, y + 2)
				if (r1, c1, r2, c2) in dic:
					mn = min(mn, 1 + dic[r1, c1, r2, c2])
				elif inB(r1, c1) and inB(r2, c2) and (grid[r2][c2] == 0) and ((r1, c1, r2, c2) not in visited):
					mn = min(mn, 1 + dfs(r1, c1, r2, c2, visited))
				(r1, c1, r2, c2) = (x + 1, y, x + 1, y + 1)
				if (r1, c1, r2, c2) in dic:
					mn = min(mn, 1 + dic[r1, c1, r2, c2])
				elif inB(r1, c1) and inB(r2, c2) and (grid[r1][c1] == 0) and (grid[r2][c2] == 0) and ((r1, c1, r2, c2) not in visited):
					mn = min(mn, 1 + dfs(r1, c1, r2, c2, visited))
				(r1, c1, r2, c2) = (x, y, x + 1, y)
				if (r1, c1, r2, c2) in dic:
					mn = min(mn, 1 + dic[r1, c1, r2, c2])
				elif inB(r1, c1) and inB(r2, c2) and (grid[r2][c2] == 0) and (grid[r2][c2 + 1] == 0) and ((r1, c1, r2, c2) not in visited):
					mn = min(mn, 1 + dfs(r1, c1, r2, c2, visited))
			else:
				(r1, c1, r2, c2) = (x + 1, y, x + 2, y)
				if (r1, c1, r2, c2) in dic:
					mn = min(mn, 1 + dic[r1, c1, r2, c2])
				elif inB(r1, c1) and inB(r2, c2) and (grid[r2][c2] == 0) and ((r1, c1, r2, c2) not in visited):
					mn = min(mn, 1 + dfs(r1, c1, r2, c2, visited))
				(r1, c1, r2, c2) = (x, y + 1, x + 1, y + 1)
				if (r1, c1, r2, c2) in dic:
					mn = min(mn, 1 + dic[r1, c1, r2, c2])
				elif inB(r1, c1) and inB(r2, c2) and (grid[r1][c1] == 0) and (grid[r2][c2] == 0) and ((r1, c1, r2, c2) not in visited):
					mn = min(mn, 1 + dfs(r1, c1, r2, c2, visited))
				(r1, c1, r2, c2) = (x, y, x, y + 1)
				if (r1, c1, r2, c2) in dic:
					mn = min(mn, 1 + dic[r1, c1, r2, c2])
				elif inB(r1, c1) and inB(r2, c2) and (grid[r2 + 1][c2] == 0) and (grid[r2][c2] == 0) and ((r1, c1, r2, c2) not in visited):
					mn = min(mn, 1 + dfs(r1, c1, r2, c2, visited))
			dic[x1, y1, x2, y2] = mn
			return mn
		d = dfs(0, 0, 0, 1, set())
		return d if d != float('inf') else -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		start = (0, 0, 0)
		end = (n - 1, n - 2, 0)
		queue = {start}
		seen = set()
		steps = 0
		while queue:
			newQueue = set()
			for (i, j, d) in queue:
				if (i, j, d) == end:
					return steps
				seen.add((i, j, d))
				if d == 0:
					if j + 2 < n and (not grid[i][j + 2]):
						if (i, j + 1, 0) not in seen:
							newQueue.add((i, j + 1, 0))
					if i + 1 < n and (not grid[i + 1][j]) and (not grid[i + 1][j + 1]):
						if (i + 1, j, 0) not in seen:
							newQueue.add((i + 1, j, 0))
						if (i, j, 1) not in seen:
							newQueue.add((i, j, 1))
				else:
					if i + 2 < n and (not grid[i + 2][j]):
						if (i + 1, j, 1) not in seen:
							newQueue.add((i + 1, j, 1))
					if j + 1 < n and (not grid[i][j + 1]) and (not grid[i + 1][j + 1]):
						if (i, j + 1, 1) not in seen:
							newQueue.add((i, j + 1, 1))
						if (i, j, 0) not in seen:
							newQueue.add((i, j, 0))
			queue = newQueue
			steps += 1
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		if not grid[n - 1][n - 2] == grid[n - 1][n - 1] == 0:
			return -1
		locs = set([(0, 0, 'h')])
		visited = set(locs)
		time = 0
		while locs and (n - 1, n - 2, 'h') not in locs and ((n - 1, n - 2, 'h') not in locs):
			time += 1
			new_locs = set()
			for (i, j, align) in locs:
				if align == 'h' and j + 2 < n and ((i, j + 1, 'h') not in visited) and (not grid[i][j + 2]):
					new_locs.add((i, j + 1, 'h'))
				if align == 'v' and j + 1 < n and ((i, j + 1, 'v') not in visited) and (not grid[i][j + 1]) and (not grid[i + 1][j + 1]):
					new_locs.add((i, j + 1, 'v'))
				if align == 'h' and i + 1 < n and ((i + 1, j, 'h') not in visited) and (not grid[i + 1][j]) and (not grid[i + 1][j + 1]):
					new_locs.add((i + 1, j, 'h'))
				if align == 'v' and i + 2 < n and ((i + 1, j, 'v') not in visited) and (not grid[i + 2][j]):
					new_locs.add((i + 1, j, 'v'))
				if align == 'h' and i + 1 < n and ((i, j, 'v') not in visited) and (not grid[i + 1][j]) and (not grid[i + 1][j + 1]):
					new_locs.add((i, j, 'v'))
				if align == 'v' and j + 1 < n and ((i, j, 'h') not in visited) and (not grid[i][j + 1]) and (not grid[i + 1][j + 1]):
					new_locs.add((i, j, 'h'))
			locs = set(new_locs)
			visited |= locs
		if (n - 1, n - 2, 'h') in locs or (n - 1, n - 2, 'h') in locs:
			return time
		else:
			return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		orientation = 'h'
		(head, tail) = ((0, 1), (0, 0))
		q = collections.deque()
		q.append((head, tail, orientation))
		visited = set()
		visited.add((head, tail, orientation))
		moves = 0
		n = len(grid)
		(target_head, target_tail) = ((n - 1, n - 1), (n - 1, n - 2))
		while q:
			for _ in range(len(q)):
				(head, tail, orientation) = q.popleft()
				if head == target_head and tail == target_tail:
					return moves
				(head_x, head_y) = head
				(tail_x, tail_y) = tail
				if orientation == 'h':
					if head_y + 1 < n and grid[head_x][head_y + 1] == 0:
						node = ((head_x, head_y + 1), head, orientation)
						if node not in visited:
							q.append(node)
							visited.add(node)
					if head_x + 1 < n and grid[head_x + 1][head_y] == 0 and (grid[tail_x + 1][tail_y] == 0):
						node = ((head_x + 1, head_y), (tail_x + 1, tail_y), orientation)
						if node not in visited:
							q.append(node)
							visited.add(node)
					if head_x + 1 < n and grid[head_x + 1][head_y] == 0 and (grid[head_x + 1][tail_y] == 0):
						node = ((tail_x + 1, tail_y), tail, 'v')
						if node not in visited:
							q.append(node)
							visited.add(node)
				else:
					if head_y + 1 < n and grid[head_x][head_y + 1] == 0 and (grid[tail_x][tail_y + 1] == 0):
						node = ((head_x, head_y + 1), (tail_x, tail_y + 1), 'v')
						if node not in visited:
							q.append(node)
							visited.add(node)
					if head_x + 1 < n and grid[head_x + 1][head_y] == 0:
						node = ((head_x + 1, head_y), head, 'v')
						if node not in visited:
							q.append(node)
							visited.add(node)
					if head_y + 1 < n and grid[head_x][head_y + 1] == 0 and (grid[tail_x][tail_y + 1] == 0):
						node = ((tail_x, tail_y + 1), tail, 'h')
						if node not in visited:
							q.append(node)
							visited.add(node)
			moves += 1
		return -1


class Solution:

	def bfs(self, M: List[List[List[int]]]) -> int:
		Q = deque()
		visited = set()
		Q.append((0, 0, 0, 0))
		visited.add((0, 0, 0))
		while len(Q) != 0:
			(k, i, j, depth) = Q.popleft()
			if depth > 25:
				print(k, i, j, depth)
			if (k, i, j) == (0, self.m - 1, self.n - 2):
				return depth
			if j + 1 < len(M[k][i]) and (k, i, j + 1) not in visited and (M[k][i][j + 1] == 0):
				Q.append((k, i, j + 1, depth + 1))
				visited.add((k, i, j + 1))
			if i + 1 < len(M[k]) and (k, i + 1, j) not in visited and (M[k][i + 1][j] == 0):
				Q.append((k, i + 1, j, depth + 1))
				visited.add((k, i + 1, j))
			if i + 1 < self.n and j + 1 < self.m and ((k ^ 1, i, j) not in visited) and (M[2][i][j] == 0):
				Q.append((k ^ 1, i, j, depth + 1))
				visited.add((k ^ 1, i, j))
		return -1

	def minimumMoves(self, grid: List[List[int]]) -> int:
		self.m = len(grid)
		self.n = len(grid[0])
		M = [[[0] * (self.n - 1) for i in range(self.m)], [[0] * self.n for i in range(self.m - 1)], [[0] * (self.n - 1) for i in range(self.m - 1)]]
		for i in range(self.m):
			for j in range(self.n):
				if j + 1 < self.n:
					M[0][i][j] = grid[i][j] | grid[i][j + 1]
				if i + 1 < self.m:
					M[1][i][j] = grid[i][j] | grid[i + 1][j]
				if i + 1 < self.m and j + 1 < self.n:
					M[2][i][j] = grid[i][j] | grid[i + 1][j] | grid[i][j + 1] | grid[i + 1][j + 1]
		return self.bfs(M)


from collections import deque

class Solution:
	dx = [1, 0]
	dy = [0, 1]

	def minimumMoves(self, grid: List[List[int]]) -> int:
		visit = set()
		q = deque()
		n = len(grid)
		answer = float('inf')
		init_pos = [0, 0, 0, 1, 1, 0]
		q.append(init_pos)
		while q:
			(x1, y1, x2, y2, is_horizon, cost) = q.popleft()
			if cost >= 20:
				print((x1, y1, x2, y2, is_horizon, cost))
			if is_horizon and x1 == n - 1 and (x2 == n - 1) and (y2 == n - 1) and (y1 == n - 2):
				answer = min(answer, cost)
			visit.add(((x1, y1), (x2, y2)))
			for i in range(2):
				nx1 = x1 + self.dx[i]
				ny1 = y1 + self.dy[i]
				nx2 = x2 + self.dx[i]
				ny2 = y2 + self.dy[i]
				if 0 <= nx1 < n and 0 <= ny1 < n and (0 <= nx2 < n) and (0 <= ny2 < n) and (grid[nx1][ny1] == 0) and (grid[nx2][ny2] == 0):
					if ((nx1, ny1), (nx2, ny2)) not in visit:
						nxt_hrizon = 1 if nx1 == nx2 else 0
						visit.add(((nx1, ny1), (nx2, ny2)))
						q.append([nx1, ny1, nx2, ny2, nxt_hrizon, cost + 1])
			if is_horizon:
				if x1 < n - 1 and grid[x1 + 1][y1] == 0 and (grid[x2 + 1][y2] == 0):
					if ((x1, y1), (x2 + 1, y2 - 1)) not in visit:
						visit.add(((x1, y1), (x2 + 1, y2 - 1)))
						q.append([x1, y1, x2 + 1, y2 - 1, 0, cost + 1])
			elif y1 < n - 1 and grid[x1][y1 + 1] == 0 and (grid[x2][y2 + 1] == 0):
				if ((x1, y1), (x2 - 1, y2 + 1)) not in visit:
					visit.add(((x1, y1), (x2 - 1, y2 + 1)))
					q.append([x1, y1, x2 - 1, y2 + 1, 1, cost + 1])
		if answer != float('inf'):
			return answer
		else:
			return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		m = n = len(grid)
		visited = {(1, 0)}
		q = collections.deque([(1, 0)])
		moves = 0
		while q:
			for _ in range(len(q)):
				(h, t) = q.popleft()
				(ti, tj) = divmod(t, n)
				(hi, hj) = divmod(h, n)
				if hi == n - 1 and hj == n - 1 and (ti == n - 1):
					return moves
				for (di, dj) in [[0, 1], [1, 0]]:
					hii = hi + di
					hjj = hj + dj
					tii = ti + di
					tjj = tj + dj
					if hii < n and hjj < n and (tii < n) and (tjj < n) and (grid[hii][hjj] != 1) and (grid[tii][tjj] != 1):
						next = (hii * n + hjj, tii * n + tjj)
						if hii == hjj == tii == n - 1:
							return moves + 1
						if next not in visited:
							q.append(next)
							visited.add(next)
						if di == 1 and hi == ti:
							next = (h + n - 1, t)
							if next not in visited:
								q.append(next)
								visited.add(next)
						if dj == 1 and hj == tj:
							next = (h - n + 1, t)
							if next not in visited:
								q.append(next)
								visited.add(next)
			moves += 1
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		n = len(grid)
		q = collections.deque()
		q.append((0, 0, 0, 0))
		visited = set()
		while q:
			(r, c, direction, steps) = q.popleft()
			if (r, c, direction) == (n - 1, n - 2, 0):
				return steps
			if (r, c, direction) not in visited:
				visited.add((r, c, direction))
				if direction:
					if c + 1 < n and grid[r][c + 1] + grid[r + 1][c + 1] == 0:
						q.append((r, c + 1, 1, steps + 1))
						q.append((r, c, 0, steps + 1))
					if r + 2 < n and grid[r + 2][c] == 0:
						q.append((r + 1, c, 1, steps + 1))
				else:
					if r + 1 < n and grid[r + 1][c] + grid[r + 1][c + 1] == 0:
						q.append((r + 1, c, 0, steps + 1))
						q.append((r, c, 1, steps + 1))
					if c + 2 < n and grid[r][c + 2] == 0:
						q.append((r, c + 1, 0, steps + 1))
		return -1


class Solution:

	def minimumMoves(self, grid: List[List[int]]) -> int:
		queue = deque()
		queue.append([0, 0, 0, 0])
		visited = {(0, 0, 0): 1}
		n = len(grid)
		while len(queue) > 0:
			(x, y, dic, step) = queue.popleft()
			if x == n - 1 and y == n - 2 and (dic == 0):
				return step
			if dic == 0:
				(nx, ny) = (x, y + 1)
				if nx >= 0 and nx < n and (ny >= 0) and (ny + 1 < n):
					if grid[nx][ny + 1] == 0 and (nx, ny, 0) not in visited:
						queue.append([nx, ny, 0, step + 1])
						visited[nx, ny, 0] = 1
				(nx, ny) = (x, y)
				(checkx1, checky1) = (x + 1, y)
				(checkx, checky) = (x + 1, y + 1)
				if checkx1 >= 0 and checkx1 < n and (checky1 >= 0) and (checky1 < n):
					if checkx >= 0 and checkx < n and (checky >= 0) and (checky < n):
						if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and ((nx, ny, 1) not in visited):
							queue.append([nx, ny, 1, step + 1])
							visited[nx, ny, 1] = 1
						if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and ((checkx1, checky1, 0) not in visited):
							queue.append([checkx1, checky1, 0, step + 1])
							visited[checkx1, checky1, 0] = 1
			if dic == 1:
				(nx, ny) = (x + 1, y)
				if nx >= 0 and nx + 1 < n and (ny >= 0) and (ny < n):
					if grid[nx + 1][ny] == 0 and (nx, ny, 1) not in visited:
						queue.append([nx, ny, 1, step + 1])
						visited[nx, ny, 1] = 1
				(nx, ny) = (x, y)
				(checkx1, checky1) = (x, y + 1)
				(checkx, checky) = (x + 1, y + 1)
				if checkx1 >= 0 and checkx1 < n and (checky1 >= 0) and (checky1 < n):
					if checkx >= 0 and checkx < n and (checky >= 0) and (checky < n):
						if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and ((nx, ny, 0) not in visited):
							queue.append([nx, ny, 0, step + 1])
							visited[nx, ny, 0] = 1
						if grid[checkx1][checky1] == 0 and grid[checkx][checky] == 0 and ((x, y + 1, 1) not in visited):
							queue.append([x, y + 1, 1, step + 1])
							visited[x, y + 1, 1] = 1
		return -1