#c #recursion #backtracking
#c #рекурсия #отслеживание назад #отслеживание возврата
Вопрос:
Я пытаюсь решить вопрос 489 Leetcode. Робот-уборщик комнат с использованием обратного отслеживания. В частности, я пытаюсь перемещать робота в каждом из 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() возвращает false, и функция возвращается перед очисткой верхнего левого угла.
Я был бы признателен за любые предложения о том, что может пойти не так.
Код:
struct hsh {
size_t operator() (const pair<int,int>amp; 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(Robotamp; 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, Robotamp; 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(Robotamp; 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(Robotamp; 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;
}
};
Ответ №1:
Проблема заключалась в том, что интерфейс класса робота не возвращает робота автоматически при возврате (объект робота передается по ссылке и сохраняет свое положение). Добавление определенной функции для перемещения робота обратно после возврата исправило проблему:
void go_back(Robotamp; 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, Robotamp; 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);
}
}
}
}
Ответ №2:
Пожалуйста, взгляните на подробное объяснение и код ниже:-
'''
The robot will start from (0,0) moving right (from top left)
When the Robot hits (X or 1) robot will turn the clock and move
example:
- moving right then hits (X) or reaches the end of Rooms.
- the robot will move down and keep moving until it hits (X) or reach the bottom
- the robot will move left and keep moving until it hits (X) or reach the first room (index=0)
- the robot will move up and keep moving until it hits (X) or reach the Top first room (index=0)
- room will be count once so if the robot cross one room more thank one time its still count as one.
'''
def RobotMove(x, y, direction, array, cleaned, looping):
# Need check as function need exit condition to work correctly
# I put 20X20 it was the rule that max rooms are 20
if looping > 400:
# print("Exit With Rooms cleanes", len(cleaned))
return len(cleaned)
else:
looping_new = looping 1
max_Y_axis = len(array)
max_X_axis = len(array[0])
if direction == "right":
if x 1 < max_X_axis:
if array[y][x 1] != 1:
# print("Go right")
# print("Room number cleared is ", str(x) "|" str(y))
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x 1, y, "right", array, cleaned, looping_new)
else:
# print("Room number cleared is ", str(x) "|" str(y))
# print("Go Down", x, y)
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "down", array, cleaned, looping_new)
else:
# print("Room number cleared is ", str(x) "|" str(y))
# print("Go Down", x, y)
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "down", array, cleaned, looping_new)
if direction == "down":
if y 1 < max_Y_axis:
if array[y 1][x] != 1:
# print("Go down")
# print("Room number cleared is ", str(x) "|" str(y))
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y 1, "down", array, cleaned, looping_new)
else:
# print("Room number cleared is ", str(x) "|" str(y))
# print("Go Down", x, y)
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "left", array, cleaned, looping_new)
else:
# print("Room number cleared is ", str(x) "|" str(y))
# print("Go Down", x, y)
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "left", array, cleaned, looping_new)
if direction == "left":
# print("Current point", str(x) "|" str(y))
# print("Next point", str(int(x)-1) "|" str(y))
if x-1 > -1:
# print("Value is ", array[y][x-1])
if array[y][x-1] != 1:
# print("Go left")
# print("Room number cleared is ", str(x) "|" str(y))
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x-1, y, "left", array, cleaned, looping_new)
else:
# print("Room number cleared is ", str(x) "|" str(y))
# print("Go left", x, y)
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "up", array, cleaned, looping_new)
else:
# print("Room number cleared is ", str(x) "|" str(y))
# print("Go left", x, y)
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "up", array, cleaned, looping_new)
if direction == "up":
if y-1 > -1:
if array[y-1][x] != 1:
# print("Go up")
# print("Room number cleared is ", str(x) "|" str(y))
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y-1, "up", array, cleaned, looping_new)
else:
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "right", array, cleaned, looping_new)
else:
if str(x) "|" str(y) not in cleaned:
cleaned.append(str(x) "|" str(y))
return RobotMove(x, y, "right", array, cleaned, looping_new)
# Output: Total number of Cleaned Rooms 13
Room = [
[0, 0, 0, 0, 0, 1],
[0, 1, 0, 0, 0, 1],
[0, 0, 0, 1, 0, 1],
[1, 0, 0, 0, 0, 1]
]
print("Total number of Cleaned Rooms", RobotMove(0, 0, "right", Room, [], 0))
Комментарии:
1. Не объясняет, что пошло не так с попыткой пользователя и кодом на неправильном языке.