Strictly speaking, the main part of this answer can be called "Not an answer." So first, consider the actual question:
What is the algorithm that detects all cells with minimal rotations?
Answer. At each step, you can calculate all the possible successors to the current state. Then the successors of these successors. This can be repeated recursively until one of the successors contains more # fields. The sequence of states through which this successor was reached is optimal in terms of the number of moves necessary to achieve this state.
This is still trivial. But, of course, this is not possible for a "big" card and / or a "large" number of workers.
As mentioned in the comments: I believe that finding the optimal solution can be an NP-complete problem. In any case, this is, in all likelihood, at least an extremely complex optimization problem, where you can use some fairly sophisticated methods to find the optimal solution at the optimal time.
So, IMHO, the only possible approach to solve this problem is heuristic.
Here you can introduce several approaches. However, I wanted to try using a very simple approach. The following MCVEs accept the definition of a map as a rectangular line (empty spaces are "invalid" areas, so you can imagine non-rectangular maps with them). Workers are simply listed, from 0 to 9 (limited to this number at the moment). The string is converted to MapState , which consists of the actual map, as well as the paths that workers have so far gone.
The actual search here is the “greedy” version of the exhaustive search that I described in the first paragraph: given the initial state, it computes all successor states. These are the states in which each employee moved in any direction (for example, 64 states for 3 workers - of course, they are "filtered" to make sure that the workers do not leave the map or go to the same field).
These successor states are stored in the list. He then searches for a list for the “best” state and again computes all the successors to this “best” state and stores them in the list. Sooner or later, the list contains a state in which there are no fields.
Determining the “best” state is where the heuristic comes into play: the state is “better” than the other when there are fewer fields (not considered). When two states have an equal number of missing fields, then the average distance of the workers to the next unreviewed fields serves as a criterion for determining which one is “better”.
This also finds the solution for the example, which is contained in the code below, rather quickly and prints it in the form of lists of positions that each worker should visit for each move.
Of course, this also does not apply to "really big" cards or "many" workers, because the list of states will grow quite quickly (you might think about discarding the "worst" solutions in order to speed it up a bit, but this may have reservations , for example, stuck in local optima). In addition, you can easily think of cases where a “greedy” strategy does not give optimal results. But until someone puts MVCE, which always calculates the optimal solution in polynomial time, maybe someone will find this interesting or useful.
import java.awt.Point; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; public class MapExplorerTest { public static void main(String[] args) { String mapString = " ### ######"+"\n"+ " ### ###1##"+"\n"+ "###############"+"\n"+ "#0#############"+"\n"+ "###############"+"\n"+ "###############"+"\n"+ "###############"+"\n"+ "###############"+"\n"+ "###############"+"\n"+ "###############"+"\n"+ "##### #######"+"\n"+ "##### #######"+"\n"+ "##### #######"+"\n"+ "###############"+"\n"+ "###############"+"\n"+ "###############"+"\n"+ "### ######2##"+"\n"+ "### #########"+"\n"; MapExplorer m = new MapExplorer(mapString); MapState solution = m.computeSolutionGreedy(); System.out.println(solution.createString()); } } class MapState { private int rows; private int cols; private char map[][]; List<List<Point>> workerPaths; private int missingFields = -1; MapState(String mapString) { workerPaths = new ArrayList<List<Point>>(); rows = countLines(mapString); cols = mapString.indexOf("\n"); map = new char[rows][cols]; String s = mapString.replaceAll("\\n", ""); for (int r=0; r<rows; r++) { for (int c=0; c<cols; c++) { int i = c+r*cols; char ch = s.charAt(i); map[r][c] = ch; if (Character.isDigit(ch)) { int workerIndex = ch - '0'; while (workerPaths.size() <= workerIndex) { workerPaths.add(new ArrayList<Point>()); } Point p = new Point(r, c); workerPaths.get(workerIndex).add(p); } } } } MapState(MapState other) { this.rows = other.rows; this.cols = other.cols; this.map = new char[other.map.length][]; for (int i=0; i<other.map.length; i++) { this.map[i] = other.map[i].clone(); } this.workerPaths = new ArrayList<List<Point>>(); for (List<Point> otherWorkerPath : other.workerPaths) { this.workerPaths.add(MapExplorer.copy(otherWorkerPath)); } } int distanceToMissing(Point p0) { if (getMissingFields() == 0) { return -1; } List<Point> points = new ArrayList<Point>(); Map<Point, Integer> distances = new HashMap<Point, Integer>(); distances.put(p0, 0); points.add(p0); while (!points.isEmpty()) { Point p = points.remove(0); List<Point> successors = MapExplorer.computeSuccessors(p); for (Point s : successors) { if (!isValid(p)) { continue; } if (map[px][py] == '#') { return distances.get(p)+1; } if (!distances.containsKey(s)) { distances.put(s, distances.get(p)+1); points.add(s); } } } return -1; } double averageDistanceToMissing() { double d = 0; for (List<Point> workerPath : workerPaths) { Point p = workerPath.get(workerPath.size()-1); d += distanceToMissing(p); } return d / workerPaths.size(); } int getMissingFields() { if (missingFields == -1) { missingFields = countMissingFields(); } return missingFields; } private int countMissingFields() { int count = 0; for (int r=0; r<rows; r++) { for (int c=0; c<cols; c++) { if (map[r][c] == '#') { count++; } } } return count; } void update() { for (List<Point> workerPath : workerPaths) { Point p = workerPath.get(workerPath.size()-1); for (int dr=-1; dr<=1; dr++) { for (int dc=-1; dc<=1; dc++) { if (dr == 0 && dc == 0) { continue; } int nr = px + dr; int nc = py + dc; if (!isValid(nr, nc)) { continue; } if (map[nr][nc] != '#') { continue; } map[nr][nc] = '.'; } } } } public void updateWorkerPosition(int w, Point p) { List<Point> workerPath = workerPaths.get(w); Point old = workerPath.get(workerPath.size()-1); char oc = map[old.x][old.y]; char nc = map[px][py]; map[old.x][old.y] = nc; map[px][py] = oc; } boolean isValid(int r, int c) { if (r < 0) return false; if (r >= rows) return false; if (c < 0) return false; if (c >= cols) return false; if (map[r][c] == ' ') { return false; } return true; } boolean isValid(Point p) { return isValid(px, py); } private static int countLines(String s) { int count = 0; while (s.contains("\n")) { s = s.replaceFirst("\\\n", ""); count++; } return count; } public String createMapString() { StringBuilder sb = new StringBuilder(); for (int r=0; r<rows; r++) { for (int c=0; c<cols; c++) { sb.append(map[r][c]); } sb.append("\n"); } return sb.toString(); } public String createString() { StringBuilder sb = new StringBuilder(); for (List<Point> workerPath : workerPaths) { Point p = workerPath.get(workerPath.size()-1); int d = distanceToMissing(p); sb.append(workerPath).append(", distance: "+d+"\n"); } sb.append(createMapString()); sb.append("Missing "+getMissingFields()); return sb.toString(); } } class MapExplorer { MapState mapState; public MapExplorer(String mapString) { mapState = new MapState(mapString); mapState.update(); computeSuccessors(mapState); } static List<Point> copy(List<Point> list) { List<Point> result = new ArrayList<Point>(); for (Point p : list) { result.add(new Point(p)); } return result; } public MapState computeSolutionGreedy() { Comparator<MapState> comparator = new Comparator<MapState>() { @Override public int compare(MapState ms0, MapState ms1) { int m0 = ms0.getMissingFields(); int m1 = ms1.getMissingFields(); if (m0 != m1) { return m0-m1; } double d0 = ms0.averageDistanceToMissing(); double d1 = ms1.averageDistanceToMissing(); return Double.compare(d0, d1); } }; Set<MapState> handled = new HashSet<MapState>(); List<MapState> list = new ArrayList<MapState>(); list.add(mapState); while (true) { MapState best = list.get(0); for (MapState mapState : list) { if (!handled.contains(mapState)) { if (comparator.compare(mapState, best) < 0) { best = mapState; } } } if (best.getMissingFields() == 0) { return best; } handled.add(best); list.addAll(computeSuccessors(best)); System.out.println("List size "+list.size()+", handled "+handled.size()+", best\n"+best.createString()); } } List<MapState> computeSuccessors(MapState mapState) { int numWorkers = mapState.workerPaths.size(); List<Point> oldWorkerPositions = new ArrayList<Point>(); for (int i=0; i<numWorkers; i++) { List<Point> workerPath = mapState.workerPaths.get(i); Point p = workerPath.get(workerPath.size()-1); oldWorkerPositions.add(p); } List<List<Point>> successorPositionsForWorkers = new ArrayList<List<Point>>(); for (int w=0; w<oldWorkerPositions.size(); w++) { Point p = oldWorkerPositions.get(w); List<Point> ps = computeSuccessors(p); successorPositionsForWorkers.add(ps); } List<List<Point>> newWorkerPositionsList = new ArrayList<List<Point>>(); int numSuccessors = (int)Math.pow(4, numWorkers); for (int i=0; i<numSuccessors; i++) { String s = Integer.toString(i, 4); while (s.length() < numWorkers) { s = "0"+s; } List<Point> newWorkerPositions = copy(oldWorkerPositions); for (int w=0; w<numWorkers; w++) { int index = s.charAt(w) - '0'; Point newPosition = successorPositionsForWorkers.get(w).get(index); newWorkerPositions.set(w, newPosition); } newWorkerPositionsList.add(newWorkerPositions); } List<MapState> successors = new ArrayList<MapState>(); for (int i=0; i<newWorkerPositionsList.size(); i++) { List<Point> newWorkerPositions = newWorkerPositionsList.get(i); if (workerPositionsValid(newWorkerPositions)) { MapState successor = new MapState(mapState); for (int w=0; w<numWorkers; w++) { Point p = newWorkerPositions.get(w); successor.updateWorkerPosition(w, p); successor.workerPaths.get(w).add(p); } successor.update(); successors.add(successor); } } return successors; } private boolean workerPositionsValid(List<Point> workerPositions) { Set<Point> set = new HashSet<Point>(); for (Point p : workerPositions) { if (!mapState.isValid(px, py)) { return false; } set.add(p); } return set.size() == workerPositions.size(); } static List<Point> computeSuccessors(Point p) { List<Point> result = new ArrayList<Point>(); result.add(new Point(p.x+0, p.y+1)); result.add(new Point(p.x+0, py-1)); result.add(new Point(p.x+1, p.y+0)); result.add(new Point(px-1, p.y+0)); return result; } }