We are given a 2-dimensional grid. "." is an empty cell, "#" is a wall, "@" is the starting point, ("a", "b", ...) are keys, and ("A", "B", ...) are locks.
We start at the starting point, and one move consists of walking one space in one of the 4 cardinal directions.  We cannot walk outside the grid, or walk into a wall.  If we walk over a key, we pick it up.  We can't walk over a lock unless we have the corresponding key.
For some 1 <= K <= 6, there is exactly one lowercase and one uppercase letter of the first K letters of the English alphabet in the grid.  This means that there is exactly one key for each lock, and one lock for each key; and also that the letters used to represent the keys and locks were chosen in the same order as the English alphabet.
Return the lowest number of moves to acquire all keys.  If it's impossible, return -1.
 

Example 1:
Input: ["@.a.#","###.#","b.A.B"]
Output: 8


Example 2:
Input: ["@..aA","..B#.","....b"]
Output: 6


 
Note:

1 <= grid.length <= 30
1 <= grid[0].length <= 30
grid[i][j] contains only '.', '#', '@', 'a'-'f' and 'A'-'F'
The number of keys is in [1, 6].  Each key has a different letter and opens exactly one lock.

Source: leetcode | Difficulty: MEDIUM
Tags: Matrices

Bit manipulation

Data structures

Graph traversal

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

Solutions:
import heapq
from collections import deque, defaultdict

class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		key_lock_loc = {ch: (i, j) for (i, row) in enumerate(grid) for (j, ch) in enumerate(row) if ch not in {'.', '#'}}
		key_cnt = sum((key_lock in ('a', 'b', 'c', 'd', 'e', 'f') for key_lock in key_lock_loc))

		def bfs_from(src):
			(i, j) = key_lock_loc[src]
			seen = defaultdict(lambda : False)
			seen[i, j] = True
			dque = deque([(i, j, 0)])
			dist = {}
			while dque:
				(i, j, d) = dque.popleft()
				ch = grid[i][j]
				if ch != src and ch != '.':
					dist[ch] = d
					continue
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if not (0 <= x < m and 0 <= y < n) or grid[x][y] == '#' or seen[x, y]:
						continue
					seen[x, y] = True
					dque.append((x, y, d + 1))
			return dist
		dists = {key_lock: bfs_from(key_lock) for key_lock in key_lock_loc}
		all_keys_bitmap = 2 ** key_cnt - 1
		hq = [(0, '@', 0)]
		final_dist = defaultdict(lambda : float('inf'))
		final_dist['@', 0] = 0
		while hq:
			(d, ch, keys_bitmap) = heapq.heappop(hq)
			if final_dist[ch, keys_bitmap] < d:
				continue
			if keys_bitmap == all_keys_bitmap:
				return d
			for (next_key_lock, d2) in list(dists[ch].items()):
				keys_bitmap2 = keys_bitmap
				if next_key_lock.islower():
					keys_bitmap2 |= 1 << ord(next_key_lock) - ord('a')
				elif next_key_lock.isupper():
					if not keys_bitmap & 1 << ord(next_key_lock) - ord('A'):
						continue
				if d + d2 < final_dist[next_key_lock, keys_bitmap2]:
					final_dist[next_key_lock, keys_bitmap2] = d + d2
					heapq.heappush(hq, (d + d2, next_key_lock, keys_bitmap2))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid) -> int:
		from collections import deque
		import copy
		rows = len(grid)
		if rows == 0:
			return 0
		cols = len(grid[0])
		dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		num_keys = 0
		start = [-1, -1]
		for i in range(rows):
			for j in range(cols):
				ch = grid[i][j]
				if 0 <= ord(ch) - ord('a') <= 5:
					num_keys += 1
				if ch == '@':
					start[0] = i
					start[1] = j
		curr_level = deque()
		next_level = deque()
		visited = set()
		visited.add((0, start[0], start[1]))
		curr_level.append((0, start[0], start[1]))
		steps = 0
		while len(curr_level) > 0:
			for i in range(len(curr_level)):
				(ori_keys, x, y) = curr_level.popleft()
				for d in dirs:
					keys = ori_keys
					new_x = x + d[0]
					new_y = y + d[1]
					if new_x < 0 or new_x >= rows or new_y < 0 or (new_y >= cols):
						continue
					ch = grid[new_x][new_y]
					if ch == '#':
						continue
					ascii_minus_lower = ord(ch) - ord('a')
					ascii_minus_upper = ord(ch) - ord('A')
					if 0 <= ascii_minus_lower <= 5:
						keys |= 1 << ascii_minus_lower
						if keys == (1 << num_keys) - 1:
							return steps + 1
					if 0 <= ascii_minus_upper <= 5 and keys >> ascii_minus_upper & 1 == 0:
						continue
					if (keys, new_x, new_y) not in visited:
						visited.add((keys, new_x, new_y))
						next_level.append((keys, new_x, new_y))
			curr_level = copy.deepcopy(next_level)
			next_level.clear()
			steps += 1
		return -1


class Solution:

	def __init__(self):
		self.DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		(start_x, start_y) = (-1, -1)
		target_keys = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					(start_x, start_y) = (i, j)
				elif grid[i][j] in 'abcdef':
					target_keys |= 1 << ord(grid[i][j]) - ord('a')
		pq = [(0, 0, start_x, start_y)]
		visited = set((0, start_x, start_y))
		while pq:
			(curr_steps, curr_keys, x, y) = heapq.heappop(pq)
			if curr_keys == target_keys:
				return curr_steps
			for (delta_x, delta_y) in self.DIR:
				(next_x, next_y) = (x + delta_x, y + delta_y)
				if not self.inbound(grid, next_x, next_y) or grid[next_x][next_y] == '#':
					continue
				if grid[next_x][next_y] in 'ABCDEF':
					if curr_keys >> ord(grid[next_x][next_y]) - ord('A') & 1:
						next_keys = curr_keys
					else:
						continue
				elif grid[next_x][next_y] in 'abcdef':
					next_keys = curr_keys | 1 << ord(grid[next_x][next_y]) - ord('a')
				else:
					next_keys = curr_keys
				if (next_keys, next_x, next_y) in visited:
					continue
				heapq.heappush(pq, (curr_steps + 1, next_keys, next_x, next_y))
				visited.add((next_keys, next_x, next_y))
		return -1

	def inbound(self, grid, x, y):
		return 0 <= x < len(grid) and 0 <= y < len(grid[0])


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		m = len(grid)
		n = len(grid[0])

		def neighbor(i, j, keys):
			keys_list = list(keys)
			if grid[i][j] in ['.', '@']:
				return (i, j, keys)
			elif grid[i][j].islower():
				if grid[i][j] in keys_list:
					return (i, j, keys)
				else:
					keys_list.append(grid[i][j])
					new_keys = ''.join(keys_list)
					return (i, j, new_keys)
			elif grid[i][j].isupper():
				if grid[i][j].lower() in keys_list:
					return (i, j, keys)
			return None

		def move(i, j, keys):
			nexts = []
			if i > 0:
				nei = neighbor(i - 1, j, keys)
				if nei:
					nexts.append(nei)
			if i < m - 1:
				nei = neighbor(i + 1, j, keys)
				if nei:
					nexts.append(nei)
			if j > 0:
				nei = neighbor(i, j - 1, keys)
				if nei:
					nexts.append(nei)
			if j < n - 1:
				nei = neighbor(i, j + 1, keys)
				if nei:
					nexts.append(nei)
			return nexts

		def get_start_and_keys():
			(x, y, keys) = (-1, -1, 0)
			for i in range(m):
				for j in range(n):
					if grid[i][j] == '@':
						(x, y) = (i, j)
					elif grid[i][j].islower():
						keys += 1
			return (x, y, keys)
		(i0, j0, total_keys) = get_start_and_keys()
		q = deque()
		start_point = (i0, j0, '')
		q.append(start_point)
		visited = set()
		visited.add(start_point)
		steps = -1
		while q:
			size = len(q)
			steps += 1
			for x in range(size):
				pop = q.popleft()
				i = pop[0]
				j = pop[1]
				keys = pop[2]
				if len(keys) == total_keys:
					return steps
				for nex in move(i, j, keys):
					if nex not in visited:
						q.append(nex)
						visited.add(nex)
		return -1


import heapq
from collections import deque, defaultdict

class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		key_lock_loc = {ch: (i, j) for (i, row) in enumerate(grid) for (j, ch) in enumerate(row) if ch not in {'.', '#'}}

		def bfs_from(src):
			(i, j) = key_lock_loc[src]
			seen = [[False] * n for _ in range(m)]
			seen[i][j] = True
			dque = deque([(i, j, 0)])
			dist = {}
			while dque:
				(i, j, d) = dque.popleft()
				ch = grid[i][j]
				if ch != src and ch != '.':
					dist[ch] = d
					continue
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if not (0 <= x < m and 0 <= y < n) or grid[x][y] == '#' or seen[x][y]:
						continue
					seen[x][y] = True
					dque.append((x, y, d + 1))
			return dist
		dists = {key_lock: bfs_from(key_lock) for key_lock in key_lock_loc}
		target_state = 2 ** sum((key_lock.islower() for key_lock in key_lock_loc)) - 1
		hq = [(0, '@', 0)]
		final_dist = defaultdict(lambda : float('inf'))
		final_dist['@', 0] = 0
		while hq:
			(d, loc, state) = heapq.heappop(hq)
			if final_dist[loc, state] < d:
				continue
			if state == target_state:
				return d
			for (destination, d2) in list(dists[loc].items()):
				state2 = state
				if destination.islower():
					state2 |= 1 << ord(destination) - ord('a')
				elif destination.isupper():
					if not state & 1 << ord(destination) - ord('A'):
						continue
				if d + d2 < final_dist[destination, state2]:
					final_dist[destination, state2] = d + d2
					heapq.heappush(hq, (d + d2, destination, state2))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		keylock = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'A': 'a', 'B': 'b', 'C': 'c', 'D': 'd', 'E': 'e', 'F': 'f'}
		m = len(grid)
		n = len(grid[0])
		keys_target = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					start = (i, j)
				elif grid[i][j] in 'abcdef':
					keys_target = keys_target | 1 << keylock[grid[i][j]]

		def keyAllAcquired(value):
			if value & keys_target == keys_target:
				return True
			else:
				return False

		def isMovable(i, j):
			if 0 <= i <= m - 1 and 0 <= j <= n - 1 and (grid[i][j] != '#'):
				return True
			else:
				return False
		visited_states = {(start[0], start[1], 0)}
		q = collections.deque()
		q.append((start[0], start[1], 0))
		step = 0
		while q:
			q_len = len(q)
			for _ in range(q_len):
				(i, j, keys) = q.popleft()
				if keyAllAcquired(keys):
					return step
				directs = [-1, 0, 1, 0, -1]
				for d in range(4):
					newi = i + directs[d]
					newj = j + directs[d + 1]
					if isMovable(newi, newj):
						if grid[newi][newj] in 'abcdef':
							new_state = (newi, newj, keys | 1 << keylock[grid[newi][newj]])
							if new_state not in visited_states:
								visited_states.add(new_state)
								q.append(new_state)
						elif grid[newi][newj] in 'ABCDEF':
							lower_int = keylock[keylock[grid[newi][newj]]]
							new_state = (newi, newj, keys | 1 << lower_int + 6)
							if keys & 1 << lower_int and new_state not in visited_states:
								visited_states.add(new_state)
								q.append(new_state)
						elif grid[newi][newj] in '.@' and (newi, newj, keys) not in visited_states:
							visited_states.add((newi, newj, keys))
							q.append((newi, newj, keys))
			step += 1
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(row, col) = (len(grid), len(grid[0]))
		(x, y) = (None, None)
		num_keys = 0
		for r in range(row):
			for c in range(col):
				if grid[r][c] == '@':
					(x, y) = (r, c)
				elif grid[r][c] in 'abcdef':
					num_keys += 1
		queue = collections.deque([(x, y, 0, 0, '.@abcdef')])
		dires = [1, 0, -1, 0, 1]
		visited = set()
		while queue:
			(r, c, steps, cnt_keys, accessible) = queue.popleft()
			if grid[r][c] in 'abcdef' and grid[r][c].upper() not in accessible:
				accessible += grid[r][c].upper()
				cnt_keys += 1
			if cnt_keys == num_keys:
				return steps
			for d in range(len(dires) - 1):
				(new_r, new_c) = (r + dires[d], c + dires[d + 1])
				if 0 <= new_r < row and 0 <= new_c < col and (grid[r][c] in accessible):
					if (new_r, new_c, accessible) not in visited:
						visited.add((new_r, new_c, accessible))
						queue.append((new_r, new_c, steps + 1, cnt_keys, accessible))
		return -1


from collections import defaultdict, deque
import heapq

class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		oa = ord('a')
		oA = ord('A')
		(m, n) = (len(grid), len(grid[0]))
		key_lock_loc = {ch: (i, j) for (i, row) in enumerate(grid) for (j, ch) in enumerate(row) if ch not in '#.'}
		key_cnt = sum((ch.islower() for ch in key_lock_loc))

		def dfs_from(src):
			(i, j) = key_lock_loc[src]
			seen = defaultdict(lambda : False)
			seen[i, j] = True
			dque = deque([(i, j, 0)])
			dist = {}
			while dque:
				(i, j, d) = dque.popleft()
				ch = grid[i][j]
				if ch != src and ch != '.':
					dist[ch] = d
					continue
				for (x, y) in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):
					if not (0 <= x < m and 0 <= y < n) or grid[x][y] == '#' or seen[x, y]:
						continue
					dque.append((x, y, d + 1))
					seen[x, y] = True
			return dist
		dists = {ch: dfs_from(ch) for ch in key_lock_loc}
		target_state = 2 ** key_cnt - 1
		final_dist = defaultdict(lambda : float('inf'))
		hq = [(0, '@', 0)]
		final_dist['@', 0] = 0
		while hq:
			(d, ch, state) = heapq.heappop(hq)
			if d > final_dist[ch, state]:
				continue
			if state == target_state:
				return d
			for (ch1, d1) in dists[ch].items():
				state1 = state
				if ch1.islower():
					state1 |= 1 << ord(ch1) - oa
				elif ch1.isupper() and (not state1 & 1 << ord(ch1) - oA):
					continue
				if d + d1 < final_dist[ch1, state1]:
					final_dist[ch1, state1] = d + d1
					heapq.heappush(hq, (d + d1, ch1, state1))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid):
		(m, n, k, keys, d) = (len(grid), len(grid[0]), 0, '', set())
		grid.append('#' * n)
		for i in range(m):
			grid[i] += '#'
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					(si, sj) = (i, j)
				elif grid[i][j] in 'abcdef':
					keys += grid[i][j]
		(a, keyss) = ([(si, sj, keys)], ''.join([c.upper() for c in keys]))
		while a:
			b = []
			for (i, j, keys) in a:
				keys = keys.replace(grid[i][j], '')
				if not keys:
					return k
				for (ii, jj) in ((i, j + 1), (i + 1, j), (i, j - 1), (i - 1, j)):
					if grid[ii][jj] != '#' and (not (grid[ii][jj] in keyss and grid[ii][jj].lower() in keys)) and ((ii, jj, keys) not in d):
						d.add((ii, jj, keys))
						b.append((ii, jj, keys))
			(a, k) = (b, k + 1)
		return -1


class Solution:

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

		def bfs(r, c):
			start = grid[r][c]
			dist[start] = {}
			queue = collections.deque([(r, c, 0)])
			visited = {(r, c): True}
			while queue:
				(i, j, d) = queue.pop()
				if grid[i][j] not in ['.', '#', start]:
					dist[start][grid[i][j]] = d
					continue
				for (ic, jc) in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:
					if 0 <= ic < m and 0 <= jc < n and ((ic, jc) not in visited) and (grid[ic][jc] != '#'):
						visited[ic, jc] = True
						queue.appendleft((ic, jc, d + 1))
		(m, n) = (len(grid), len(grid[0]))
		dist = {}
		for r in range(m):
			for c in range(n):
				if grid[r][c] not in ['.', '#']:
					bfs(r, c)
		prioq = [(0, '@', 0)]
		target_state = 0
		visited = {}
		for key in dist:
			if 'a' <= key <= 'f':
				target_state += 1 << ord(key) - ord('a')
		while prioq:
			(d, p, state) = heapq.heappop(prioq)
			if (p, state) in visited:
				continue
			if state == target_state:
				return d
			visited[p, state] = True
			for (dest, moves) in list(dist[p].items()):
				if 'A' <= dest <= 'F' and 1 << ord(dest) - ord('A') & state == 0:
					continue
				new_state = state
				if 'a' <= dest <= 'f':
					new_state |= 1 << ord(dest) - ord('a')
				if (dest, new_state) not in visited:
					heapq.heappush(prioq, (d + moves, dest, new_state))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		m = len(grid)
		n = len(grid[0])
		q = collections.deque()
		keys = 0
		visited = set()
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					q.append((i, j, 0))
					visited.add((i, j, 0))
				elif grid[i][j] >= 'a' and grid[i][j] <= 'f':
					keys += 1
		goal = (1 << keys) - 1
		dirs = [[-1, 0], [1, 0], [0, -1], [0, 1]]
		step = 0
		while q:
			size = len(q)
			for _ in range(size):
				(i, j, state) = q.popleft()
				for (di, dj) in dirs:
					x = i + di
					y = j + dj
					if x < 0 or x >= m or y < 0 or (y >= n) or (grid[x][y] == '#') or ((x, y, state) in visited):
						continue
					nstate = state
					if grid[x][y] >= 'A' and grid[x][y] <= 'F':
						temp = ord(grid[x][y]) - ord('A')
						if state & 1 << temp == 0:
							continue
					elif grid[x][y] >= 'a' and grid[x][y] <= 'f':
						temp = ord(grid[x][y]) - ord('a')
						nstate |= 1 << temp
						if nstate == goal:
							return step + 1
					visited.add((x, y, nstate))
					q.append((x, y, nstate))
			step += 1
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(init_x, init_y) = (-1, -1)
		m = len(grid)
		n = len(grid[0])
		keycnt = 0
		for i in range(m):
			for j in range(n):
				c = grid[i][j]
				if c == '@':
					(init_x, init_y) = (i, j)
				if c >= 'a' and c <= 'f':
					keycnt += 1
		init_state = (0, init_x, init_y)
		q = collections.deque()
		visited = set()
		visited.add(init_state)
		q.append(init_state)
		steps = -1
		finalkey = 0
		for i in range(keycnt):
			finalkey |= 1 << i
		while q:
			lens = len(q)
			steps += 1
			for _ in range(len(q)):
				(keys, x, y) = q.popleft()
				for (nx, ny) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
					if 0 > nx or nx >= m or 0 > ny or (ny >= n):
						continue
					new_s = keys
					c = grid[nx][ny]
					if c == '#':
						continue
					if c >= 'A' and c <= 'F' and (keys >> ord(c) - ord('A') & 1 == 0):
						continue
					if c >= 'a' and c <= 'f':
						new_s |= 1 << ord(c) - ord('a')
					if (new_s, nx, ny) in visited:
						continue
					if new_s == finalkey:
						return steps + 1
					visited.add((new_s, nx, ny))
					q.append((new_s, nx, ny))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		if not grid:
			return -1
		keys = [0] * 6
		(m, n) = (len(grid), len(grid[0]))
		(si, sj) = (0, 0)
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					(si, sj) = (i, j)
				if grid[i][j].islower():
					keys[ord(grid[i][j]) - ord('a')] = 1
		mykeys = tuple(keys)
		q = [(si, sj, tuple([0] * 6))]
		visited = {(si, sj, tuple([0] * 6))}
		c = 0
		while q:
			nextq = []
			for (i, j, keys) in q:
				for (x, y) in ((i + 1, j), (i - 1, j), (i, j - 1), (i, j + 1)):
					if 0 <= x < m and 0 <= y < n and (grid[x][y] != '#'):
						if grid[x][y] in '.@':
							if (x, y, keys) not in visited:
								nextq.append((x, y, keys))
								visited.add((x, y, keys))
						elif grid[x][y].islower():
							okeys = list(keys)
							okeys[ord(grid[x][y]) - ord('a')] = 1
							nkeys = tuple(okeys)
							if nkeys == mykeys:
								return c + 1
							elif (x, y, nkeys) not in visited:
								nextq.append((x, y, nkeys))
								visited.add((x, y, nkeys))
						elif grid[x][y].isupper():
							if keys[ord(grid[x][y].lower()) - ord('a')] == 1 and (x, y, keys) not in visited:
								nextq.append((x, y, keys))
								visited.add((x, y, keys))
			c += 1
			q = nextq
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		keys = 'abcdef'
		locks = 'ABCDEF'
		(n, m) = (len(grid), len(grid[0]))
		(x, y) = (-1, -1)
		target = 0
		for i in range(n):
			for j in range(m):
				ch = grid[i][j]
				if ch == '@':
					(x, y) = (i, j)
				elif ch in keys:
					idx = keys.find(ch)
					target |= 1 << idx
		visited = set()
		visited.add((x, y, 0))
		q = deque()
		q.append((x, y, 0, 0))
		while q:
			(x, y, state, move) = q.popleft()
			if state == target:
				return move
			for (dx, dy) in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
				dx += x
				dy += y
				tmp = state
				if dx < 0 or dy < 0 or dx >= n or (dy >= m):
					continue
				ch = grid[dx][dy]
				if ch == '#':
					continue
				if ch in locks:
					idx = locks.find(ch)
					if state & 1 << idx == 0:
						continue
				if ch in keys:
					idx = keys.find(ch)
					tmp |= 1 << idx
				if (dx, dy, tmp) not in visited:
					visited.add((dx, dy, tmp))
					q.append((dx, dy, tmp, move + 1))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		q = collections.deque()
		seen = set()
		tot_keys = 0
		for (i, row) in enumerate(grid):
			for (j, val) in enumerate(row):
				if val == '@':
					q.append((i, j, 0))
					seen.add((i, j, 0))
				elif val in 'ABCDEF':
					tot_keys += 1
		steps = 0
		while q:
			N = len(q)
			for _ in range(N):
				(x, y, keys) = q.popleft()
				if keys == (1 << tot_keys) - 1:
					return steps
				for (nx, ny) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
					if 0 <= nx < m and 0 <= ny < n:
						if grid[nx][ny] == '#':
							continue
						if grid[nx][ny] in 'ABCDEF' and (not keys >> ord(grid[nx][ny]) - ord('A') & 1):
							continue
						nxt = keys
						if grid[nx][ny] in 'abcdef':
							nxt |= 1 << ord(grid[nx][ny]) - ord('a')
						if (nx, ny, nxt) not in seen:
							seen.add((nx, ny, nxt))
							q.append((nx, ny, nxt))
			steps += 1
		return -1


from collections import deque

class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
		m = len(grid)
		n = len(grid[0])
		visited = set()
		q = deque()
		cnt = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					q.append((i, j, 0))
					visited.add((i, j, 0))
				elif grid[i][j] in 'abcdef':
					cnt += 1
		keys = set('abcdef')
		locks = set('ABCDEF')
		target = 2 ** cnt - 1
		steps = 0
		while len(q) > 0:
			q_sz = len(q)
			for _ in range(q_sz):
				(x, y, cur_keys) = q.popleft()
				if cur_keys == target:
					return steps
				for d in dirs:
					(next_x, next_y) = (x + d[0], y + d[1])
					pos_flag = False
					if 0 <= next_x < m and 0 <= next_y < n and (grid[next_x][next_y] != '#'):
						new_keys = cur_keys
						if grid[next_x][next_y] in locks:
							lock = ord(grid[next_x][next_y]) - ord('A')
							if 1 << lock & cur_keys != 0:
								pos_flag = True
						elif grid[next_x][next_y] in keys:
							key = ord(grid[next_x][next_y]) - ord('a')
							new_keys = cur_keys | 1 << key
							pos_flag = True
						else:
							pos_flag = True
						if pos_flag and (next_x, next_y, new_keys) not in visited:
							visited.add((next_x, next_y, new_keys))
							q.append((next_x, next_y, new_keys))
			steps += 1
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		if not grid:
			return -1
		(m, n) = (len(grid), len(grid[0]))
		numKeys = 0
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					start = (i, j, 0)
				elif ord('a') <= ord(grid[i][j]) <= ord('f'):
					numKeys += 1
		bfs = [start]
		seen = set()
		d = [1, 0, -1, 0, 1]
		step = 0
		while bfs:
			(cur, bfs) = (bfs, [])
			for (x, y, keys) in cur:
				if keys == (1 << numKeys) - 1:
					return step
				for i in range(4):
					(xx, yy) = (x + d[i], y + d[i + 1])
					if 0 <= xx < m and 0 <= yy < n and ((xx, yy, keys) not in seen):
						seen.add((xx, yy, keys))
						if ord('a') <= ord(grid[xx][yy]) <= ord('f'):
							bfs.append((xx, yy, keys | 1 << ord(grid[xx][yy]) - ord('a')))
						elif ord('A') <= ord(grid[xx][yy]) <= ord('F'):
							if 1 << ord(grid[xx][yy].lower()) - ord('a') & keys == 0:
								continue
							else:
								bfs.append((xx, yy, keys))
						elif grid[xx][yy] == '.' or grid[xx][yy] == '@':
							bfs.append((xx, yy, keys))
			step += 1
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		mx_key = max((grid[i][j] for i in range(len(grid)) for j in range(len(grid[0])) if grid[i][j].isalpha() and grid[i][j].islower()))
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == '@':
					(si, sj) = (i, j)
					break
		needed_keys = (1 << ord(mx_key) - ord('a') + 1) - 1

		def key_id(c):
			if c.isupper():
				return (ord(c) - ord('A'), True)
			return (ord(c) - ord('a'), False)
		seen = {(si, sj, 0)}
		q = deque([(0, si, sj, 0)])
		while q:
			(cost, i, j, keys) = q.popleft()
			if keys == needed_keys:
				return cost
			for (ni, nj) in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
				if not 0 <= ni < len(grid) or not 0 <= nj < len(grid[0]) or grid[ni][nj] == '#':
					continue
				new_keys = keys
				if grid[ni][nj].isalpha():
					(idx, capped) = key_id(grid[ni][nj])
					if capped:
						if not keys & 1 << idx:
							continue
					else:
						new_keys |= 1 << idx
				if (ni, nj, new_keys) in seen:
					continue
				seen.add((ni, nj, new_keys))
				q.append((cost + 1, ni, nj, new_keys))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		if not grid or not grid[0]:
			return -1
		(m, n) = (len(grid), len(grid[0]))
		sx = sy = target = -1
		for i in range(m):
			for j in range(n):
				c = grid[i][j]
				if c == '@':
					(sx, sy) = (i, j)
				if c >= 'a' and c <= 'f':
					target = max(target, ord(c) - ord('a') + 1)
		target = (1 << target) - 1
		q = deque([(sx, sy, 0)])
		visited = set()
		visited.add(q[0])
		step = 0
		while q:
			for _ in range(len(q)):
				(x, y, key) = q.popleft()
				if key == target:
					return step
				for (i, j) in [[0, 1], [1, 0], [0, -1], [-1, 0]]:
					if x + i >= 0 and x + i < m and (y + j >= 0) and (y + j < n):
						c = grid[x + i][y + j]
						new_key = key
						if c == '#':
							continue
						if c >= 'A' and c <= 'F' and (key >> ord(c) - ord('A') & 1 == 0):
							continue
						if c >= 'a' and c <= 'f':
							new_key |= 1 << ord(c) - ord('a')
						if (x + i, y + j, new_key) not in visited:
							visited.add((x + i, y + j, new_key))
							q.append((x + i, y + j, new_key))
			step += 1
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		import heapq
		import collections
		(R, C) = (len(grid), len(grid[0]))
		location = {v: (r, c) for (r, row) in enumerate(grid) for (c, v) in enumerate(row) if v not in '.#'}

		def neighbors(r, c):
			for (cr, cc) in ((r - 1, c), (r, c - 1), (r + 1, c), (r, c + 1)):
				if 0 <= cr < R and 0 <= cc < C:
					yield (cr, cc)

		def bfs_from(source):
			(r, c) = location[source]
			seen = [[False] * C for _ in range(R)]
			seen[r][c] = True
			queue = collections.deque([(r, c, 0)])
			dist = {}
			while queue:
				(r, c, d) = queue.popleft()
				if source != grid[r][c] != '.':
					dist[grid[r][c]] = d
					continue
				for (cr, cc) in neighbors(r, c):
					if grid[cr][cc] != '#' and (not seen[cr][cc]):
						seen[cr][cc] = True
						queue.append((cr, cc, d + 1))
			return dist
		dists = {place: bfs_from(place) for place in location}
		target_state = 2 ** sum((p.islower() for p in location)) - 1
		pq = [(0, '@', 0)]
		final_dist = collections.defaultdict(lambda : float('inf'))
		final_dist['@', 0] = 0
		while pq:
			(d, place, state) = heapq.heappop(pq)
			if final_dist[place, state] < d:
				continue
			if state == target_state:
				return d
			for (destination, d2) in dists[place].items():
				state2 = state
				if destination.islower():
					state2 |= 1 << ord(destination) - ord('a')
				elif destination.isupper():
					if not state & 1 << ord(destination) - ord('A'):
						continue
				if d + d2 < final_dist[destination, state2]:
					final_dist[destination, state2] = d + d2
					heapq.heappush(pq, (d + d2, destination, state2))
		return -1


class Solution:

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

		def have_keys(status, key_id):
			return status & 2 ** key_id
		(sx, sy) = (-1, -1)
		key_number = 0
		key_idx = 'abcdef'
		lock_idx = 'ABCDEF'
		(n, m) = (len(grid), len(grid[0]))
		for i in range(n):
			for j in range(m):
				if grid[i][j] == '@':
					(sx, sy) = (i, j)
				elif grid[i][j] in key_idx:
					key_number = max(key_number, key_idx.find(grid[i][j]))
		final_ownkey = 2 ** (key_number + 1) - 1
		(head, queue) = (0, [(sx, sy, 0)])
		moves = [(0, 1), (0, -1), (1, 0), (-1, 0)]
		visited = {(sx, sy, 0): 0}
		while head < len(queue):
			(x, y, status) = queue[head]
			step = visited[queue[head]]
			for (dx, dy) in moves:
				(tx, ty, new_status) = (x + dx, y + dy, status)
				if n > tx >= 0 and m > ty >= 0:
					if grid[tx][ty] == '#':
						continue
					if grid[tx][ty] in lock_idx and (not have_keys(new_status, lock_idx.find(grid[tx][ty]))):
						continue
					if grid[tx][ty] in key_idx and (not have_keys(new_status, key_idx.find(grid[tx][ty]))):
						new_status += 2 ** key_idx.find(grid[tx][ty])
					if new_status == final_ownkey:
						return step + 1
					if (tx, ty, new_status) not in visited:
						queue.append((tx, ty, new_status))
						visited[tx, ty, new_status] = step + 1
			head += 1
		return -1


class Solution:

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

		def contains(k, v):
			return k // v % 2 == 1
		adjs = [[-1, 0], [0, 1], [0, -1], [1, 0]]
		keys = ['a', 'b', 'c', 'd', 'e', 'f']
		locks = [c.upper() for c in keys]
		key_to_val = {k: 2 ** i for (i, k) in enumerate(keys)}
		lock_to_val = {k: 2 ** i for (i, k) in enumerate(locks)}
		(N, M) = (len(grid), len(grid[0]))
		visited = [[[-1] * 64 for _ in range(M)] for _ in range(N)]
		queue = deque()
		target = 0
		for i in range(N):
			for j in range(M):
				if grid[i][j] == '@':
					queue.append([i, j, 0])
					visited[i][j][0] = 0
				if grid[i][j] in keys:
					target += key_to_val[grid[i][j]]
		if target == 0:
			return 0
		while len(queue) > 0:
			(i, j, k) = queue.popleft()
			for (di, dj) in adjs:
				(ii, jj) = (i + di, j + dj)
				if ii >= 0 and jj >= 0 and (ii < N) and (jj < M):
					if grid[ii][jj] in ('.', '@') and visited[ii][jj][k] < 0:
						visited[ii][jj][k] = visited[i][j][k] + 1
						queue.append((ii, jj, k))
					elif grid[ii][jj] in keys:
						if not contains(k, key_to_val[grid[ii][jj]]):
							kk = k + key_to_val[grid[ii][jj]]
							if kk == target:
								return visited[i][j][k] + 1
						else:
							kk = k
						if visited[ii][jj][kk] < 0:
							visited[ii][jj][kk] = visited[i][j][k] + 1
							queue.append((ii, jj, kk))
					elif grid[ii][jj] in locks and contains(k, lock_to_val[grid[ii][jj]]) and (visited[ii][jj][k] < 0):
						visited[ii][jj][k] = visited[i][j][k] + 1
						queue.append((ii, jj, k))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(res, dire, all_keys) = (0, [[0, 1], [1, 0], [0, -1], [-1, 0]], 0)
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == '@':
					loc = (i, j)
				if grid[i][j] in 'abcdef':
					all_keys += 1
		(cur, seen) = (set([(loc, ())]), set([(loc, ())]))

		def checker(loc, keys, di):
			(x, y) = (loc[0] + di[0], loc[1] + di[1])
			if 0 <= x < len(grid) and 0 <= y < len(grid[0]):
				t = grid[x][y]
				if t in '@.' or t in keys or (t in 'ABCDEF' and str.lower(t) in keys):
					return (((x, y), keys), False)
				if t in 'abcdef':
					newkeys = tuple(sorted(set(list(keys) + [t])))
					if len(newkeys) == all_keys:
						return (True, True)
					return (((x, y), newkeys), False)
			return (False, False)
		while cur:
			(res, tmp) = (res + 1, [])
			for node in cur:
				(loc, keys) = node
				for di in dire:
					(new_node, state) = checker(loc, keys, di)
					if state:
						return res
					if new_node not in seen and new_node:
						tmp += [new_node]
			cur = set(tmp)
			seen |= cur
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		from collections import deque
		start = [0, 0]
		numofKeys = 0
		m = len(grid)
		n = len(grid[0])
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					start = [i, j]
				if grid[i][j].isalpha():
					numofKeys += 1
		numofKeys //= 2
		keys = 0
		visited = set()
		stack = deque([[start[0], start[1], 0, 0]])
		while stack:
			(i, j, keys, count) = stack.popleft()
			for (a, b) in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
				if 0 <= a < m and 0 <= b < n:
					if grid[a][b].isalpha() and ord('a') <= ord(grid[a][b]) <= ord('f'):
						newkeys = keys | 1 << ord(grid[a][b]) - ord('a')
					elif grid[a][b].isalpha() and keys & 1 << ord(grid[a][b]) - ord('A'):
						newkeys = keys
					elif grid[a][b].isalpha() or grid[a][b] == '#':
						continue
					else:
						newkeys = keys
					if newkeys == 2 ** numofKeys - 1:
						return count + 1
					elif (a, b, newkeys) in visited:
						continue
					else:
						visited.add((a, b, newkeys))
						stack.append((a, b, newkeys, count + 1))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid) -> int:
		(row, col) = (len(grid), len(grid[0]))
		(key_num, key) = (0, {})
		for i in range(row):
			for j in range(col):
				if grid[i][j] == '@':
					(start_i, start_j) = (i, j)
				if grid[i][j] in 'abcdef' and grid[i][j] not in key:
					key[grid[i][j]] = key_num
					key_num += 1
		q = [(start_i, start_j, 0, 0)]
		visited = set()
		while q:
			l = len(q)
			for _ in range(l):
				(i, j, state, step) = q.pop(0)
				if state == (1 << key_num) - 1:
					return step
				if (i, j, state) in visited:
					continue
				visited.add((i, j, state))
				for (m, n) in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
					if 0 <= m < row and 0 <= n < col and (grid[m][n] != '#'):
						if grid[m][n] in 'abcdef':
							q.append((m, n, state | 1 << key[grid[m][n]], step + 1))
						elif grid[m][n] == '.' or grid[m][n] == '@':
							q.append((m, n, state, step + 1))
						elif grid[m][n] in 'ABCDEF':
							if state >> key[grid[m][n].lower()] & 1 == 0:
								continue
							q.append((m, n, state, step + 1))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(R, C) = (len(grid), len(grid[0]))
		(ii, jj) = (0, 0)
		target = 0
		for i in range(R):
			for j in range(C):
				if grid[i][j] == '@':
					(ii, jj) = (i, j)
				if grid[i][j].islower():
					target += 1

		def bfs(i, j):
			from collections import deque
			Q = deque([(i, j, 0, set())])
			seen = {(i, j, tuple(sorted(set())))}
			while Q:
				(i, j, d, s) = Q.popleft()
				for (di, dj) in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
					(r, c) = (i + di, j + dj)
					if 0 <= r < R and 0 <= c < C:
						if grid[r][c].islower():
							s1 = s.copy()
							s1.add(grid[r][c])
							if len(s1) == target:
								return d + 1
							tuple_s = tuple(sorted(set(s1)))
							if (r, c, tuple_s) not in seen:
								seen.add((r, c, tuple_s))
								Q.append((r, c, d + 1, s1))
						elif grid[r][c].isupper():
							if grid[r][c].lower() in s:
								tuple_s = tuple(sorted(set(s)))
								if (r, c, tuple_s) not in seen:
									seen.add((r, c, tuple_s))
									Q.append((r, c, d + 1, s))
						elif grid[r][c] != '#':
							tuple_s = tuple(sorted(set(s)))
							if (r, c, tuple_s) not in seen:
								seen.add((r, c, tuple_s))
								Q.append((r, c, d + 1, s))
			return -1
		return bfs(ii, jj)


class Solution:

	def __init__(self):
		self.DIR = [(1, 0), (-1, 0), (0, 1), (0, -1)]

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		init_x = init_y = -1
		target_keys = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if grid[i][j] == '@':
					(init_x, init_y) = (i, j)
				elif grid[i][j].islower():
					target_keys |= 1 << ord(grid[i][j]) - ord('a')
		pq = [(0, 0, init_x, init_y)]
		visited = set((0, init_x, init_y))
		while pq:
			(curr_steps, curr_keys, x, y) = heapq.heappop(pq)
			if curr_keys == target_keys:
				return curr_steps
			for (delta_x, delta_y) in self.DIR:
				(next_x, next_y) = (x + delta_x, y + delta_y)
				if not self.inbound(grid, next_x, next_y) or grid[next_x][next_y] == '#':
					continue
				if grid[next_x][next_y].isupper():
					if curr_keys >> ord(grid[next_x][next_y]) - ord('A') & 1:
						next_keys = curr_keys
					else:
						continue
				elif grid[next_x][next_y].islower():
					next_keys = curr_keys | 1 << ord(grid[next_x][next_y]) - ord('a')
				else:
					next_keys = curr_keys
				if (next_keys, next_x, next_y) in visited:
					continue
				heapq.heappush(pq, (curr_steps + 1, next_keys, next_x, next_y))
				visited.add((next_keys, next_x, next_y))
		return -1

	def inbound(self, grid, x, y):
		return 0 <= x < len(grid) and 0 <= y < len(grid[0])


from collections import deque
dirs = [(0, -1), (0, 1), (-1, 0), (1, 0)]

class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		k = 0
		(m, n) = (len(grid), len(grid[0]))
		(sr, sc) = (None, None)
		for r in range(m):
			for c in range(n):
				if grid[r][c] == '@':
					(sr, sc) = (r, c)
				elif grid[r][c] in 'abcdefABCDEF':
					k = max(k, ord(grid[r][c].lower()) - ord('a') + 1)
		dp = [[[float('inf') for z in range(1 << k)] for y in range(n)] for x in range(m)]
		dp[sr][sc][0] = 0
		dq = deque([(sr, sc, 0, 0)])
		while dq:
			size = len(dq)
			for i in range(size):
				(r, c, ks, s) = dq.popleft()
				for d in dirs:
					(nr, nc) = (r + d[0], c + d[1])
					if not 0 <= nr < m or not 0 <= nc < n:
						continue
					elif grid[nr][nc] == '#':
						continue
					elif grid[nr][nc] in '.@':
						if s + 1 < dp[nr][nc][ks]:
							dp[nr][nc][ks] = s + 1
							dq.append((nr, nc, ks, s + 1))
					elif grid[nr][nc] in 'ABCDEF':
						lock = ord(grid[nr][nc]) - ord('A')
						if ks & 1 << lock:
							if s + 1 < dp[nr][nc][ks]:
								dp[nr][nc][ks] = s + 1
								dq.append((nr, nc, ks, s + 1))
					elif grid[nr][nc] in 'abcdef':
						key = ord(grid[nr][nc]) - ord('a')
						nks = ks | 1 << key
						if s + 1 < dp[nr][nc][nks]:
							dp[nr][nc][nks] = s + 1
							dq.append((nr, nc, nks, s + 1))
		ret = float('inf')
		for r in range(m):
			for c in range(n):
				ret = min(ret, dp[r][c][-1])
		return ret if ret != float('inf') else -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		k = 0
		(stx, sty) = (0, 0)
		for i in range(m):
			for j in range(n):
				if grid[i][j] in 'abcdef':
					k += 1
				if grid[i][j] == '@':
					stx = i
					sty = j

		def keys(mask):
			ans = 0
			for m in [1, 2, 4, 8, 16, 32]:
				if mask & m:
					ans += 1
			return ans

		def neighbors(i, j):
			for (dx, dy) in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
				if i + dx < 0 or i + dx >= m or j + dy < 0 or (j + dy >= n):
					continue
				if grid[i + dx][j + dy] == '#':
					continue
				yield (i + dx, j + dy)
		q = collections.deque()
		seen = set()
		q.append((stx, sty, 0, 0))
		while q:
			(i, j, mask, moves) = q.popleft()
			if grid[i][j] in 'ABCDEF':
				id = 'ABCDEF'.index(grid[i][j])
				if not mask & 1 << id:
					continue
			if (i, j, mask) in seen:
				continue
			seen.add((i, j, mask))
			if keys(mask) == k:
				return moves - 1
			if grid[i][j] in 'abcdef':
				mask |= 1 << ord(grid[i][j]) - ord('a')
			for (ii, jj) in neighbors(i, j):
				q.append((ii, jj, mask, moves + 1))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		from heapq import heappush, heappop
		(R, C) = (len(grid), len(grid[0]))
		start = None
		K = 0
		for r in range(R):
			for c in range(C):
				if grid[r][c] == '@':
					start = (r, c)
				elif grid[r][c].isupper():
					K = max(K, ord(grid[r][c]) - ord('A') + 1)
		assert start is not None
		assert K > 0
		h = [(0, *start, 0)]
		seen = set()
		while h:
			(m, r, c, keys) = heappop(h)
			if (r, c, keys) in seen:
				continue
			seen.add((r, c, keys))
			if keys == (1 << K) - 1:
				return m
			for (rp, cp) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
				if 0 <= rp < R and 0 <= cp < C:
					char = grid[rp][cp]
					if char == '#' or (char.isupper() and keys & 1 << ord(char) - ord('A') == 0):
						continue
					new_keys = keys
					if char.islower():
						new_keys |= 1 << ord(char) - ord('a')
					heappush(h, (m + 1, rp, cp, new_keys))
		return -1


from collections import deque

class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		keyMap = {ch: 1 << offset for (offset, ch) in enumerate('abcdef')}

		def hasKey(state, key):
			return state & keyMap[key]

		def setKey(state, key):
			return state | keyMap[key]
		keys = set()
		start = None
		target = 0
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if 'a' <= grid[i][j] <= 'f':
					target = setKey(target, grid[i][j])
				elif grid[i][j] == '@':
					start = (i, j)

		def neighbors(i, j):
			moves = [(1, 0), (-1, 0), (0, 1), (0, -1)]
			for (di, dj) in moves:
				if 0 <= i + di < len(grid) and 0 <= j + dj < len(grid[0]) and (grid[i][j] != '#'):
					yield (i + di, j + dj)
		visited = set()
		q = deque([[start, 0, 0]])
		while q:
			(coord, oldKeys, steps) = q.popleft()
			for n in neighbors(coord[0], coord[1]):
				newKeys = oldKeys
				c = grid[n[0]][n[1]]
				if 'A' <= c <= 'F' and (not hasKey(newKeys, c.lower())):
					continue
				if 'a' <= c <= 'f':
					newKeys = setKey(newKeys, c)
				if newKeys == target:
					return steps + 1
				if (n, newKeys) not in visited:
					visited.add((n, newKeys))
					q.append([n, newKeys, steps + 1])
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(sr, sc) = (0, 0)
		(k, m, n) = (0, len(grid), len(grid[0]))
		key_id = collections.defaultdict(int)
		for (i, x) in enumerate('abcdef'):
			key_id[x] = i + 1
		for r in range(m):
			for c in range(n):
				if grid[r][c] == '@':
					(sr, sc) = (r, c)
				k = max(k, key_id[grid[r][c]])
		q = [(sr, sc, '')]
		res = 0
		vis = set((sr, sc, ''))
		while q:
			tmp = []
			for (r, c, keys) in q:
				if len(keys) == k:
					return res
				for (rr, cc) in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
					if 0 <= rr < m and 0 <= cc < n and (grid[rr][cc] != '#'):
						x = grid[rr][cc]
						if x in 'ABCDEF' and x.lower() not in keys:
							continue
						new_keys = keys[:]
						if x in 'abcdef' and x not in new_keys:
							new_keys += x
						if (rr, cc, new_keys) not in vis:
							vis.add((rr, cc, new_keys))
							tmp.append((rr, cc, new_keys))
			res += 1
			q = tmp
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		(startx, starty) = (-1, -1)
		nkeys = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == '@':
					(startx, starty) = (i, j)
				if grid[i][j] in 'abcdef':
					nkeys += 1
		queue = deque([(startx, starty, 0, '', 0)])
		visited = set([(startx, starty, '')])
		while queue:
			node = queue.popleft()
			(x, y, nkey, keys, moves) = node
			if nkey == nkeys:
				return moves
			for ni in [(x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1)]:
				(xx, yy) = ni
				if xx < 0 or yy < 0 or xx >= n or (yy >= m) or (grid[xx][yy] == '#'):
					continue
				if grid[xx][yy] in 'ABCDEF':
					if grid[xx][yy].lower() in keys and (xx, yy, keys) not in visited:
						queue.append((xx, yy, nkey, keys, moves + 1))
						visited.add((xx, yy, keys))
				elif grid[xx][yy] in 'abcdef' and grid[xx][yy] not in keys:
					visited.add((xx, yy, keys + grid[xx][yy]))
					queue.append((xx, yy, nkey + 1, keys + grid[xx][yy], moves + 1))
				elif (xx, yy, keys) not in visited:
					visited.add((xx, yy, keys))
					queue.append((xx, yy, nkey, keys, moves + 1))
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(m, n) = (len(grid), len(grid[0]))
		(q, seen, keys) = (deque(), set(), set())
		for i in range(m):
			for j in range(n):
				if grid[i][j] == '@':
					q.append((i, j, ''))
					seen.add((i, j, ''))
				elif 'a' <= grid[i][j] <= 'f':
					keys.add(grid[i][j])
		steps = 0
		while q:
			size = len(q)
			for _ in range(size):
				(x, y, k) = q.popleft()
				if len(k) == len(keys):
					return steps
				for (i, j) in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
					(nx, ny, nk) = (x + i, y + j, k)
					if nx < 0 or nx >= m or ny < 0 or (ny >= n) or (grid[nx][ny] == '#'):
						continue
					if 'A' <= grid[nx][ny] <= 'F' and grid[nx][ny].lower() not in nk:
						continue
					if 'a' <= grid[nx][ny] <= 'f' and grid[nx][ny] not in nk:
						nk += grid[nx][ny]
					if (nx, ny, nk) not in seen:
						q.append((nx, ny, nk))
						seen.add((nx, ny, nk))
			steps += 1
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		target = 0
		(queue, visited) = ([], set())
		for i in range(len(grid)):
			for j in range(len(grid[0])):
				if 'a' <= grid[i][j] <= 'f':
					target += 1
				elif grid[i][j] == '@':
					queue.append((i, j, '.@abcdef', 0))
					visited.add((i, j, '.@abcedf'))
		dirs = [(1, 0), (-1, 0), (0, 1), (0, -1)]
		ans = 0
		collected = set()
		while len(queue) != 0:
			size = len(queue)
			for _ in range(size):
				(x, y, bag, collected) = queue.pop(0)
				if collected == target:
					return ans
				for (ix, iy) in dirs:
					xx = x + ix
					yy = y + iy
					if 0 <= xx < len(grid) and 0 <= yy < len(grid[0]) and (grid[xx][yy] in bag):
						if 'a' <= grid[xx][yy] <= 'f' and grid[xx][yy].upper() not in bag:
							if (xx, yy, bag + grid[xx][yy].upper()) not in visited:
								queue.append((xx, yy, bag + grid[xx][yy].upper(), collected + 1))
								visited.add((xx, yy, bag + grid[xx][yy].upper()))
						elif (xx, yy, bag) not in visited:
							queue.append((xx, yy, bag, collected))
							visited.add((xx, yy, bag))
			ans += 1
		return -1


class Solution:

	def shortestPathAllKeys(self, grid: List[str]) -> int:
		(n, m) = (len(grid), len(grid[0]))
		queue = collections.deque()
		seen = set()
		nKeys = 0
		moves = 0
		for i in range(n):
			for j in range(m):
				if grid[i][j] == '@':
					queue.append([i, j, 0, 0, 'abcdef.@'])
				elif grid[i][j] in 'abcdef':
					nKeys += 1
		while queue:
			(i, j, moves, curKeys, keys) = queue.popleft()
			if grid[i][j] in 'abcdef' and grid[i][j].upper() not in keys:
				keys += grid[i][j].upper()
				curKeys += 1
			if curKeys == nKeys:
				return moves
			for (x, y) in ((-1, 0), (1, 0), (0, -1), (0, 1)):
				(ni, nj) = (i + x, j + y)
				if 0 <= ni < n and 0 <= nj < m and (grid[ni][nj] in keys) and ((ni, nj, keys) not in seen):
					seen.add((ni, nj, keys))
					queue.append([ni, nj, moves + 1, curKeys, keys])
		return -1