BFS with a queue that shuffles left

A shortest-path BFS over a grid returns correct distances and sails through the 100 × 100 test suite. On a 1000 × 1000 open grid it takes minutes, and a profiler attributes nearly all the time to a single innocuous-looking line: queue.pop(0). The algorithm is textbook BFS. Explain the slowdown, quantify it, and fix it with the right standard-library tool.

1def shortest_path(grid):
2    """Steps from top-left to bottom-right through 0-cells, or -1."""
3    rows, cols = len(grid), len(grid[0])
4    dist = [[-1] * cols for _ in range(rows)]
5    dist[0][0] = 0
6    queue = [(0, 0)]
7 
8    while queue:
9        r, c = queue.pop(0)              # dequeue from the front
10        if r == rows - 1 and c == cols - 1:
11            return dist[r][c]
12        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
13            nr, nc = r + dr, c + dc
14            if 0 <= nr < rows and 0 <= nc < cols:
15                if grid[nr][nc] == 0 and dist[nr][nc] == -1:
16                    dist[nr][nc] = dist[r][c] + 1
17                    queue.append((nr, nc))
18    return -1
19 
20 
21big = [[0] * 1000 for _ in range(1000)]
22print(shortest_path(big))                # 1998 — correct, but takes minutes

1. What does list.pop(0) cost on a list of length m, and what does CPython physically do to the underlying array?
2. Derive the overall complexity of this BFS in terms of the number of cells V and the frontier size. Why is 100 × 100 fine and 1000 × 1000 minutes?
3. Which standard-library type fixes this in two lines? What are its complexity guarantees at each end?
4. Why is queue.Queue from the queue module the *wrong* fix here despite the promising name?
5. Are list.insert(0, x), del lst[0] and lst.pop() affected the same way?
6. State the complexity before and after.