机器人穿过有障碍物的二维网格所需的时间

Question

有一个整数的二维网格，其值为 1 或 0（1 表示障碍物，0 表示陆地）。计算机器人清洁所有陆地单元所需的最短时间。机器人最初放置在 (x,y) 处。它可以向 4 个方向移动（左/右/上/下）。 帮助代码

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;
    }
}

返回机器人清洁每个陆地单元所需的最少步骤（如果机器人访问某个单元，则该单元被清洁）以及所需的最小旋转次数。 约束：需要使用 BFS 来访问单元格，而不是 DFS。

需要填写的功能：

public Pair bfs(int[][] grid, Position currentPosition, Robot robot, Direction currentDirection)

尝试了几次广度优先搜索的实现，但无法完成。 有人可以帮助完成返回最小移动次数以及所需的最小旋转次数的函数吗？有人提到你不能使用深度优先搜索，你只需要使用广度优先搜索。

Answer 1

这就是旅行商问题，这是出了名的难。您可能需要一些近似值，以便在您的特定情况下给出良好的结果，例如允许重新访问某些顶点。一个好的开始是谷歌搜索“公制旅行推销员近似”快捷方式：查看 http://www.cs.tufts.edu/~cowen/advanced/2002/adv-lect3.pdf

基本算法

1. 将网格转换为具有顶点和边的图。如果相邻单元格都没有障碍物，则将它们链接起来。

2. 找到图的最小生成树（Kruskal 或 Prim 算法）

3. 在树中搜索以找到路径，当到达叶子时回溯。

请注意，步骤 3 使用深度优先搜索。我无法想象广度优先搜索如何产生一个好的解决方案 - 每一步都会回溯以搜索其他邻接。

关于如何实现这个细节有很多详细的变化——这是一个很大的话题。要了解一些可能性，请查看 https://github.com/JamesBremner/PathFinder，特别是障碍物应用程序 https://github.com/JamesBremner/PathFinderFeb2023/wiki/Obstacles