基于BFS的带障碍二维网格机器人清扫最小动作量求解

问题描述 #

现有一个由0和1组成的二维整数网格：

• 1代表障碍
• 0代表可清扫陆地

需计算机器人清扫所有陆地单元格所需的最少移动次数与旋转次数。机器人初始位置为给定的(x,y)，可向上下左右四个方向移动。

辅助代码 #

import java.util.Objects;

interface Robot {
    boolean move(Position current, Direction direction, int[][] grid);
    Direction turnLeft(Direction currentDirection);
    Direction turnRight(Direction currentDirection);
    boolean clean();
}

class RobotImpl implements Robot {
    Position currentPosition;
    Direction currentDirection;
    int moveCount = 0;
    int rotationCount = 0;

    @Override
    public boolean move(Position current, Direction direction, int[][] grid) {
        if(current.x == grid.length || current.x < 0 || current.y == grid[0].length || current.y < 0) {
            return false;
        }
        Position newPosition = getNewPosition(current, direction);
        if(grid[newPosition.x][newPosition.y] == 1) {
            return false;
        }
        this.currentPosition = newPosition;
        moveCount++;
        return true;
    }

    private Position getNewPosition(Position current, Direction direction) {
        switch(direction) {
            case UP:
                current.y--;
                break;
            case DOWN:
                current.y++;
                break;
            case LEFT:
                current.x--;
                break;
            case RIGHT:
                current.x++;
                break;
        }
        return current;
    }

    @Override
    public Direction turnLeft(Direction currentDirection) {
        switch(currentDirection) {
            case UP:
                currentDirection = Direction.LEFT;
                break;
            case LEFT:
                currentDirection = Direction.DOWN;
                break;
            case DOWN:
                currentDirection = Direction.RIGHT;
                break;
            case RIGHT:
                currentDirection = Direction.UP;
                break;
        }
        rotationCount++;
        return currentDirection;
    }

    @Override
    public Direction turnRight(Direction currentDirection) {
        switch(currentDirection) {
            case UP:
                currentDirection = Direction.RIGHT;
                break;
            case LEFT:
                currentDirection = Direction.UP;
                break;
            case DOWN:
                currentDirection = Direction.LEFT;
                break;
            case RIGHT:
                currentDirection = Direction.DOWN;
                break;
        }
        rotationCount++;
        return currentDirection;
    }

    @Override
    public boolean clean() {
        return true;
    }
}

class Pair {
    int moves;
    int rotations;

    Pair(int moves, int rotations) {
        this.moves = moves;
        this.rotations = rotations;
    }
}

enum Direction {
    LEFT, RIGHT, UP, DOWN
}

class Position {
    int x, y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Position position = (Position) o;
        return x == position.x && y == position.y;
    }

    @Override
    public int hashCode() {
        return Objects.hash(x, y);
    }
}

实现要求 #

• 必须使用**广度优先搜索（BFS）**算法，禁止使用深度优先搜索（DFS）
• 实现public Pair bfs(int[][] grid, Position currentPosition, Robot robot, Direction currentDirection)函数，返回清扫所有陆地单元格所需的最少移动次数和旋转次数

BFS实现方案 #

核心思路 #

BFS的每个状态需包含：

1. 当前机器人的位置
2. 当前机器人的朝向
3. 已清扫的单元格标记数组
4. 累计的移动次数和旋转次数

通过队列逐层遍历所有可能的状态，优先处理步数更少的状态，第一个达成清扫所有陆地的状态即为最优解。

代码实现 #

import java.util.*;

public class RobotCleaner {
    public Pair bfs(int[][] grid, Position startPos, Robot robot, Direction startDir) {
        // 统计需清扫的陆地总数
        int totalCleanable = 0;
        int rows = grid.length;
        int cols = grid[0].length;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 0) {
                    totalCleanable++;
                }
            }
        }

        // 初始状态：已清扫起始位置
        boolean[][] initialCleaned = new boolean[rows][cols];
        initialCleaned[startPos.x][startPos.y] = true;

        // 队列存储BFS状态
        Queue<State> queue = new LinkedList<>();
        queue.add(new State(new Position(startPos.x, startPos.y), startDir, initialCleaned, 0, 0));

        // 去重集合，避免重复处理相同状态
        Set<String> visited = new HashSet<>();
        visited.add(getStateKey(startPos, startDir, initialCleaned));

        // 遍历四个可能的移动方向
        Direction[] allDirs = Direction.values();

        while (!queue.isEmpty()) {
            State current = queue.poll();

            // 已清扫所有陆地，返回结果
            if (current.cleanCount == totalCleanable) {
                return new Pair(current.moves, current.rotations);
            }

            // 尝试转向所有方向并移动
            for (Direction targetDir : allDirs) {
                if (targetDir == current.dir) {
                    // 无需旋转，直接尝试移动
                    attemptMove(current, targetDir, grid, queue, visited);
                } else {
                    // 计算最少旋转次数和目标方向
                    RotationResult rotationRes = calculateMinRotations(current.dir, targetDir, robot);
                    // 生成旋转后的状态
                    State rotatedState = new State(
                            new Position(current.pos.x, current.pos.y),
                            rotationRes.newDir,
                            current.cleaned,
                            current.moves,
                            current.rotations + rotationRes.rotationCount
                    );
                    // 尝试移动
                    attemptMove(rotatedState, rotationRes.newDir, grid, queue, visited);
                }
            }
        }

        // 无清扫需求或无法完成清扫时返回默认值
        return new Pair(0, 0);
    }

    // 尝试向目标方向移动并更新清扫状态
    private void attemptMove(State currentState, Direction targetDir, int[][] grid, Queue<State> queue, Set<String> visited) {
        Position newPos = getNewPosition(currentState.pos, targetDir);
        // 检查新位置是否合法且不是障碍
        if (newPos.x >= 0 && newPos.x < grid.length && newPos.y >= 0 && newPos.y < grid[0].length && grid[newPos.x][newPos.y] == 0) {
            boolean[][] newCleaned = copyCleanedArray(currentState.cleaned);
            int newCleanCount = currentState.cleanCount;

            // 标记新位置为已清扫（如果未清扫过）
            if (!newCleaned[newPos.x][newPos.y]) {
                newCleaned[newPos.x][newPos.y] = true;
                newCleanCount++;
            }

            String stateKey = getStateKey(newPos, targetDir, newCleaned);
            if (!visited.contains(stateKey)) {
                visited.add(stateKey);
                queue.add(new State(newPos, targetDir, newCleaned, currentState.moves + 1, currentState.rotations));
            }
        }
    }

    // 计算从当前方向到目标方向的最少旋转次数
    private RotationResult calculateMinRotations(Direction currentDir, Direction targetDir, Robot robot) {
        // 计算左转次数
        Direction tempLeft = currentDir;
        int leftCnt = 0;
        while (tempLeft != targetDir) {
            tempLeft = robot.turnLeft(tempLeft);
            leftCnt++;
        }

        // 计算右转次数
        Direction tempRight = currentDir;
        int rightCnt = 0;
        while (tempRight != targetDir) {
            tempRight = robot.turnRight(tempRight);
            rightCnt++;
        }

        // 返回次数更少的旋转方式
        return leftCnt <= rightCnt ? new RotationResult(tempLeft, leftCnt) : new RotationResult(tempRight, rightCnt);
    }

    // 生成新位置（与RobotImpl逻辑一致）
    private Position getNewPosition(Position current, Direction direction) {
        Position newPos = new Position(current.x, current.y);
        switch(direction) {
            case UP:
                newPos.y--;
                break;
            case DOWN:
                newPos.y++;
                break;
            case LEFT:
                newPos.x--;
                break;
            case RIGHT:
                newPos.x++;
                break;
        }
        return newPos;
    }

    // 复制清扫状态数组
    private boolean[][] copyCleanedArray(boolean[][] original) {
        int rows = original.length;
        int cols = original[0].length;
        boolean[][] copy = new boolean[rows][cols];
        for (int i = 0; i < rows; i++) {
            System.arraycopy(original[i], 0, copy[i], 0, cols);
        }
        return copy;
    }

    // 生成状态唯一标识key，用于去重
    private String getStateKey(Position pos, Direction dir, boolean[][] cleaned) {
        StringBuilder sb = new StringBuilder();
        sb.append(pos.x).append(",").append(pos.y).append(";");
        sb.append(dir.name()).append(";");
        for (boolean[] row : cleaned) {
            for (boolean b : row) {
                sb.append(b ? "1" : "0");
            }
            sb.append("|");
        }
        return sb.toString();
    }

    // BFS状态内部类
    private static class State {
        Position pos;
        Direction dir;
        boolean[][] cleaned;
        int moves;
        int rotations;
        int cleanCount;

        State(Position pos, Direction dir, boolean[][] cleaned, int moves, int rotations) {
            this.pos = pos;
            this.dir = dir;
            this.cleaned = cleaned;
            this.moves = moves;
            this.rotations = rotations;
            // 统计已清扫数量
            this.cleanCount = 0;
            for (boolean[] row : cleaned) {
                for (boolean b : row) {
                    if (b) cleanCount++;
                }
            }
        }
    }

    // 旋转结果内部类
    private static class RotationResult {
        Direction newDir;
        int rotationCount;

        RotationResult(Direction newDir, int rotationCount) {
            this.newDir = newDir;
            this.rotationCount = rotationCount;
        }
    }
}

关键说明 #

1. 状态去重：通过位置、方向、清扫状态组合生成唯一key，避免重复处理相同状态，提升算法效率。
2. 最少旋转策略：对每个目标方向，计算左转和右转的次数，选择次数更少的方式，保证旋转次数最优。
3. BFS特性：按层遍历确保第一个完成全清扫的状态即为最少步数解，符合题目要求的最少移动与旋转次数。

内容的提问来源于stack exchange，提问作者Mayank Sinha