Imagine doing bfs on a 2D $$$n \times n$$$ grid. Your code may look something like this:
import collections
NOT_VISITED, VISITED = 0, 1
n = int(input())
grid = [[NOT_VISITED] * n for i in range(n)]
queue = collections.deque([(0, 0)])
while len(queue):
x, y = queue.popleft()
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == NOT_VISITED:
queue.append((nx, ny))
grid[nx][ny] = VISITED
print(grid)
It works in $$$O(n^2)$$$, nothing interesting. But if we write it like this:
import collections
NOT_VISITED, VISITED = 0, 1
n = int(input())
grid = [[NOT_VISITED] * n for i in range(n)]
queue = collections.deque([(0, 0)])
while len(queue):
x, y = queue.popleft()
grid[x][y] = VISITED
for nx, ny in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == NOT_VISITED:
queue.append((nx, ny))
print(grid)
The code now works in $$$O\left(\dfrac{4^n}{\sqrt{n}}\right)$$$ :skull: :skull: :skull:
Can you figure out why?
