489. Robot Room Cleaner

leetcode hard

#backtracking#csharp#hard#hash-table#leetcode#matrix#two-pointers

Task

Вы управляете роботом в комнате, представленной бинарной сеткой m x n, где 0 — стена, а 1 — пустая ячейка.

Робот начинает в неизвестном месте, гарантированно пустом. У вас нет доступа к сетке, но вы можете перемещать робота через предоставленный API Robot.

Роботу нужно очистить всю комнату (т.е. все пустые ячейки). Он может двигаться вперед, поворачивать налево или направо на 90 градусов.

Если робот наталкивается на стену, его датчик препятствия обнаруживает это, и он остается на текущей ячейке.

C# solution

matched/original

public class Solution {
    private Robot robot;
    private HashSet<(int, int)> visited = new HashSet<(int, int)>();
    private (int, int)[] directions = { (-1, 0), (0, 1), (1, 0), (0, -1) };
    private void GoBack() {
        robot.TurnRight();
        robot.TurnRight();
        robot.Move();
        robot.TurnRight();
        robot.TurnRight();
    }
    private void Backtrack(int row, int col, int d) {
        visited.Add((row, col));
        robot.Clean();
        for (int i = 0; i < 4; ++i) {
            int newD = (d + i) % 4;
            int newRow = row + directions[newD].Item1;
            int newCol = col + directions[newD].Item2;
            if (!visited.Contains((newRow, newCol)) && robot.Move()) {
                Backtrack(newRow, newCol, newD);
                GoBack();
            }
            robot.TurnRight();
        }
    }
    public void CleanRoom(Robot robot) {
        this.robot = robot;
        Backtrack(0, 0, 0);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private Robot robot;
    private HashSet<(int, int)> visited = new HashSet<(int, int)>();
    private (int, int)[] directions = { (-1, 0), (0, 1), (1, 0), (0, -1) };
    private void GoBack() {
        robot.TurnRight();
        robot.TurnRight();
        robot.Move();
        robot.TurnRight();
        robot.TurnRight();
    }
    private void Backtrack(int row, int col, int d) {
        visited.push_back((row, col));
        robot.Clean();
        for (int i = 0; i < 4; ++i) {
            int newD = (d + i) % 4;
            int newRow = row + directions[newD].Item1;
            int newCol = col + directions[newD].Item2;
            if (!visited.Contains((newRow, newCol)) && robot.Move()) {
                Backtrack(newRow, newCol, newD);
                GoBack();
            }
            robot.TurnRight();
        }
    }
    public void CleanRoom(Robot robot) {
        this.robot = robot;
        Backtrack(0, 0, 0);
    }
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

// Auto-generated Java draft from the C# solution. Review API differences before LeetCode submit.
public class Solution {
    private Robot robot;
    private HashSet<(int, int)> visited = new HashSet<(int, int)>();
    private (int, int)[] directions = { (-1, 0), (0, 1), (1, 0), (0, -1) };
    private void GoBack() {
        robot.TurnRight();
        robot.TurnRight();
        robot.Move();
        robot.TurnRight();
        robot.TurnRight();
    }
    private void Backtrack(int row, int col, int d) {
        visited.add((row, col));
        robot.Clean();
        for (int i = 0; i < 4; ++i) {
            int newD = (d + i) % 4;
            int newRow = row + directions[newD].Item1;
            int newCol = col + directions[newD].Item2;
            if (!visited.Contains((newRow, newCol)) && robot.Move()) {
                Backtrack(newRow, newCol, newD);
                GoBack();
            }
            robot.TurnRight();
        }
    }
    public void CleanRoom(Robot robot) {
        this.robot = robot;
        Backtrack(0, 0, 0);
    }
}

JavaScript solution

matched/original

class Solution {
    constructor() {
        this.robot = null;
        this.visited = new Set();
        this.directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
    }

    goBack() {
        this.robot.turnRight();
        this.robot.turnRight();
        this.robot.move();
        this.robot.turnRight();
        this.robot.turnRight();
    }

    backtrack(row, col, d) {
        this.visited.add(`${row},${col}`);
        this.robot.clean();
        for (let i = 0; i < 4; i++) {
            const newD = (d + i) % 4;
            const newRow = row + this.directions[newD][0];
            const newCol = col + this.directions[newD][1];
            if (!this.visited.has(`${newRow},${newCol}`) && this.robot.move()) {
                this.backtrack(newRow, newCol, newD);
                this.goBack();
            }
            this.robot.turnRight();
        }
    }

    cleanRoom(robot) {
        this.robot = robot;
        this.backtrack(0, 0, 0);
    }
}

Python solution

matched/original

class Solution:
    def __init__(self):
        self.directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
        self.visited = set()
        self.robot = None

    def go_back(self):
        self.robot.turnRight()
        self.robot.turnRight()
        self.robot.move()
        self.robot.turnRight()
        self.robot.turnRight()

    def backtrack(self, row, col, d):
        self.visited.add((row, col))
        self.robot.clean()
        for i in range(4):
            new_d = (d + i) % 4
            new_row = row + self.directions[new_d][0]
            new_col = col + self.directions[new_d][1]
            if (new_row, new_col) not in self.visited and self.robot.move():
                self.backtrack(new_row, new_col, new_d)
                self.go_back()
            self.robot.turnRight()

    def cleanRoom(self, robot):
        self.robot = robot
        self.backtrack(0, 0, 0)

Go solution

matched/original

type Solution struct {
    robot     *Robot
    visited   map[[2]int]bool
    directions [4][2]int
}

func (s *Solution) goBack() {
    s.robot.TurnRight()
    s.robot.TurnRight()
    s.robot.Move()
    s.robot.TurnRight()
    s.robot.TurnRight()
}

func (s *Solution) backtrack(row, col, d int) {
    s.visited[[2]int{row, col}] = true
    s.robot.Clean()
    for i := 0; i < 4; i++ {
        newD := (d + i) % 4
        newRow := row + s.directions[newD][0]
        newCol := col + s.directions[newD][1]
        if !s.visited[[2]int{newRow, newCol}] && s.robot.Move() {
            s.backtrack(newRow, newCol, newD)
            s.goBack()
        }
        s.robot.TurnRight()
    }
}

func (s *Solution) CleanRoom(robot *Robot) {
    s.robot = robot
    s.visited = make(map[[2]int]bool)
    s.directions = [4][2]int{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}
    s.backtrack(0, 0, 0)
}

Explanation

Algorithm

interface Robot {

// возвращает true, если следующая ячейка открыта и робот перемещается в эту ячейку.

// возвращает false, если следующая ячейка является препятствием и робот остается на текущей ячейке.

boolean move();

// Робот останется на той же ячейке после вызова turnLeft/turnRight.

// Каждый поворот составляет 90 градусов.

void turnLeft();

void turnRight();

// Очистить текущую ячейку.

void clean();

}

Пример:

Input: room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3

Output: Robot cleaned all rooms.

Explanation: All grids in the room are marked by either 0 or 1.

0 means the cell is blocked, while 1 means the cell is accessible.

The robot initially starts at the position of row=1, col=3.

From the top left corner, its position is one row below and three columns right.

👨‍💻

Алгоритм:

Пометьте текущую ячейку как посещенную и очистите её.

Исследуйте четыре направления (вверх, вправо, вниз, влево) последовательно, двигаясь и очищая новые ячейки, если возможно.

Если движение невозможно (стена или посещенная ячейка), поверните направо и попробуйте снова, возвращаясь назад, если необходимо.

😎