Algorithm that discovers all the fields on a map with as least turns as possible

Question

Let's say I have such map:

#####
..###
W.###

. is a discovered cell.

# is an undiscovered cell.

W is a worker. There can be many workers. Each of them can move once per turn. In one turn he can move by one cell in 4 directions (up, right, down or left). He discovers all 8 cells around him - turns # into .. In one turn, there can be maximum one worker on the same cell.

Maps are not always rectangular. In the beginning all cells are undiscovered, except the neighbours of W.

The goal is to make all the cells discovered, in as least turns as possible.

First approach

Find the nearest # and go towards it. Repeat.

To find the nearest # I start BFS from W and finish it when first # is found.

On exemplary map it can give such solution:

##### ##### ##### ##### ##... #.... ..... 
..### ...## ....# ..... ...W. ..W.. .W... 
W.### .W.## ..W.# ...W. ..... ..... ..... 

6 turns. Pretty far from optimal:

##### ..### ...## ....# .....
..### W.### .W.## ..W.# ...W.
W.### ..### ...## ....# .....

4 turns.

Question

What is the algorithm that discovers all the cells with as least turns as possible?

Answer 1

Here is a basic idea that uses A*. It is probably quite time- and memory-consuming, but it is guaranteed to return an optimal solution and is definitely better than brute force.

The nodes for A* will be the various states, i.e. where the workers are positioned and the discovery state of all cells. Each unique state represents a different node.

Edges will be all possible transitions. One worker has four possible transitions. For more workers, you will need every possible combination (about 4^n edges). This is the part where you can constrain the workers to remain within the grid and not to overlap.

The cost will be the number of turns. The heuristic to approximate the distance to the goal (all cells discovered) can be developed as follows:

A single worker can discover at most three cells per turn. Thus, n workers can discover at most 3*n cells. The minimum number of remaining turns is therefore "number of undiscovered cells / (3 * worker count)". This is the heuristic to use. This could even be improved by determining the maximum number of cells that each worker can discover in the next turn (will be max. 3 per worker). So overall heuristic would be "(undiscorvered cells - discoverable cells) / (3 * workers) + 1".

In each step you examine the node with the least overall cost (turns so far + heuristic). For the examined node, you calculate the costs for each surrounding node (possible movements of all workers) and go on.