Leetcode 问题 489. Robot Room Cleaner - 为什么我的解决方案不起作用

Question

我正在尝试使用回溯解决 Leetcode 问题 489. Robot Room Cleaner。具体来说，我尝试在 4 个方向中的每一个方向上移动机器人，如果所有四个方向都被阻挡或清理，则返回。

下面的代码不起作用，我正在尝试用这个简单的例子来调试它：

grid = [[1,1,1],
        [1,0,1]]

其中 1 表示机器人可以访问单元格，0 表示单元格被阻止。机器人从这个初始位置开始：

initial_row = 0
initial_col = 1

在我运行我的代码之后，机器人只清洁了网格的右侧部分（c - 清洁，d - 左侧脏）：

[[d,c,c],
 [d,0,c]]

它似乎正确回溯到单元格[0,1]，并试图移动到左上角（单元格[0,0]），但是robot.move（）returns false 和函数 returns 在清理左上角之前。对于可能出现问题的任何建议，我将不胜感激。

代码：

struct hsh {
  size_t operator() (const pair<int,int>& p) const {
      hash<int> intHash;
      return intHash(p.first) ^ intHash(p.second);
  }  
};

class Solution {
public:
    unordered_set<pair<int, int>, hsh> cleaned;
    vector<int> directions {0, 1, 2, 3}; // up, down, right, left
    
    void cleanRoom(Robot& robot) {
       
        int row_s = 0; // relative start row
        int col_s = 0; // relative start col
            
        clean(row_s, col_s, robot);
    }

    void clean(int row, int col, Robot& robot) {
    
        cleaned.insert({row, col});
        robot.clean();
    
        for (int dir : directions) {
        
            if (!is_cleaned(row, col, dir)) {
                turn(robot, dir);
            
                if (robot.move()) {
                    turn_back(robot, dir);
                
                    int row_new = get_new_row(row, dir);
                    int col_new = get_new_col(col, dir);
                
                    clean(row_new, col_new, robot);
                } else {
                    turn_back(robot, dir);
                }
            }
        }
    }

    bool is_cleaned(int row, int col, int dir) {
        int row_new = get_new_row(row, dir);
        int col_new = get_new_col(col, dir);
            
        if(cleaned.find({row_new, col_new}) != cleaned.end()) {
            return true;
        }
        return false;
    
    }

    void turn(Robot& robot, int dir) {
        if (dir == 0) { // up
        } else if (dir == 1) { // down
            robot.turnLeft();
            robot.turnLeft();
        } else if (dir == 2) { // right
            robot.turnRight();
        } else { // left
            robot.turnLeft();
        }
    }

    void turn_back(Robot& robot, int dir) {
        if (dir == 0) { // back to up from up
        } else if (dir == 1) { // back to up from down
            robot.turnLeft();
            robot.turnLeft();
        } else if (dir == 2) { // back to up from right
            robot.turnLeft();
        } else { // back to up from left
            robot.turnRight();
        }
    }

    int get_new_row(int row, int dir) {
        if (dir == 0) { // up
            row--; 
            return row;
        } else if (dir == 1) { // down
            row++; 
            return row;
        }
    
        return row;
    }

    int get_new_col(int col, int dir) {
        if (dir == 2) { // right
            col++; 
            return col;
        } else if (dir == 3) { // left
            col--; 
            return col;
        }
    
        return col;
    }
};

Answer 1

问题是机器人 class 接口在回溯时不会自动将机器人放回去（机器人对象通过引用传递并保持其位置）。添加一个特定的功能来在回溯后将机器人移回修复问题：

void go_back(Robot& robot, int dir) {
    // Keep mind that the robot always ends up facing up after every move
    if (dir == 0) { // moved up - returning down
        robot.turnLeft();
        robot.turnLeft();
        robot.move();
        robot.turnLeft();
        robot.turnLeft();
    } else if (dir == 1) { // moved down - returning up
        robot.move();
    } else if (dir == 2) { // moved right - returning left
        robot.turnLeft();
        robot.move();
        robot.turnRight();
    } else { // moved left - returning right
        robot.turnRight();
        robot.move();
        robot.turnLeft();
    }
}

然后在递归clean()函数中调用这个函数：

void clean(int row, int col, Robot& robot) {
    
    cleaned.insert({row, col});
    robot.clean();
            
    for (int dir : directions) {
                    
        if (!is_cleaned(row, col, dir)) {
            turn(robot, dir);
            
            if (robot.move()) {
                turn_back(robot, dir);
                
                int row_new = get_new_row(row, dir);
                int col_new = get_new_col(col, dir);
                
                clean(row_new, col_new, robot);
                
                go_back(robot, dir); // Move the robot back while backtracking!
                
            } else {
                turn_back(robot, dir);
            }
        }
    }
    
}

Leetcode 问题 489. Robot Room Cleaner - 为什么我的解决方案不起作用

Leetcode question 489. Robot Room Cleaner - why my solution doesn't work

c++

recursion

backtracking