Caching BFS traversal in an undirected and unweighted graph

I have an undirected and unweighted graph with about a million nodes - visualized in a matrix format.

Representation of a sample graph:

The red cells are blocked.

My problem is to find the shortest distance between any two cells. The source and destination cells will be given one by one, and I need to return the shortest paths for all given cell pairs.

I looked at the following:

• the Floyd-warshall algorithm: but it takes too much memory.
• Dijkstra's algorithm for all nodes, but it is too slow.
• A* could work, but would still be slow - if the shortest path needs to be found for all pairs.

Is there any other approach for it?

Since it's just a uniform matrix, I would think that there might be some pattern I am unaware of.

Can a BFS traversal be cached somehow, so that a search can resume at an already visited node rather than starting from scratch again?