BOJ 14503 — Robot Vacuum (14503)

Problem: BOJ 14503 — Robot Vacuum · 한국어 · 日本語

The robot cleans its current cell, then turns left by 90 degrees and checks the cell ahead. It checks up to four directions in order. If it finds an uncleaned empty cell, it moves forward into that cell and starts the next iteration there. If all four directions have been checked without finding a move, it steps backward without changing its direction. It stops if the cell behind is a wall or lies outside the room. A cell is counted only once, when it is first cleaned.

At the start of each loop, mark the current cell and increment the answer only if it has not already been cleaned. Then rotate left inside a four-iteration loop and check whether each cell ahead is in bounds, empty, and uncleaned. On a successful move, immediately start the next iteration; this preserves the direction at the moment of the move rather than continuing to rotate. Only after all four checks fail, compute the cell behind using the opposite direction and move there if it is not a wall. This retreat does not change the robot’s facing direction.

Each cleanable cell is counted once, and at most four neighboring cells are checked per iteration, so the time complexity is O(NM). The room map and cleaned-cell grid each use O(NM) space.

C++17

#include <iostream>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    int row, column, direction;
    cin >> n >> m;
    cin >> row >> column >> direction;

    vector<vector<int>> room(n, vector<int>(m));
    for (auto& line : room) {
        for (int& cell : line) cin >> cell;
    }

    const int dr[4] = {-1, 0, 1, 0};
    const int dc[4] = {0, 1, 0, -1};
    vector<vector<bool>> cleaned(n, vector<bool>(m, false));
    int cleanedCount = 0;

    while (true) {
        if (!cleaned[row][column]) {
            cleaned[row][column] = true;
            ++cleanedCount;
        }

        bool moved = false;
        for (int turn = 0; turn < 4; ++turn) {
            direction = (direction + 3) % 4;
            const int nextRow = row + dr[direction];
            const int nextColumn = column + dc[direction];

            if (nextRow < 0 || nextRow >= n || nextColumn < 0 || nextColumn >= m) continue;
            if (room[nextRow][nextColumn] == 1 || cleaned[nextRow][nextColumn]) continue;

            row = nextRow;
            column = nextColumn;
            moved = true;
            break;
        }

        if (moved) continue;

        const int backDirection = (direction + 2) % 4;
        const int backRow = row + dr[backDirection];
        const int backColumn = column + dc[backDirection];
        if (backRow < 0 || backRow >= n || backColumn < 0 || backColumn >= m) break;
        if (room[backRow][backColumn] == 1) break;

        row = backRow;
        column = backColumn;
    }

    cout << cleanedCount << '\n';
    return 0;
}