Разбор задачи «Робот-уборщик»

1. Идея

Нужно честно промоделировать движение робота по клетчатому полю.

Робот начинает в клетке '@', затем по очереди выполняет k команд. Для каждой команды:

• вычисляем клетку, куда робот хочет перейти;
• если эта клетка находится внутри поля и не является перегородкой '#', то робот переходит;
• иначе остаётся на месте.

При этом надо посчитать, сколько разных клеток робот посетил. Значит, для каждой клетки нужно хранить, была ли она уже посещена.

2. Наблюдения

Наблюдение 1

Ограничения позволяют делать по одной обработке на каждую команду.

• n, m <= 1000, значит всего клеток не больше 10^6
• k <= 10^5

Если на каждом шаге делать только несколько простых действий, решение легко уложится по времени.

Наблюдение 2

Стартовая клетка '@' тоже считается свободной.

Поэтому удобно во время чтения поля:

• запомнить координаты старта;
• заменить '@' на '.'.

Тогда дальше все свободные клетки будут обрабатываться одинаково.

Наблюдение 3

Важно считать именно различные клетки.

Если робот несколько раз пришёл в одну и ту же клетку, она должна учитываться только один раз. Для этого нужен массив visited.

3. Алгоритм

1. Считываем n, m, k.
2. Считываем поле.
   • Находим клетку '@'.
   • Запоминаем её координаты sr, sc.
   • Заменяем '@' на '.'.
3. Считываем строку команд.
4. Создаём двумерный массив visited размера n x m, заполненный значением False.
5. Ставим робота в стартовую клетку:
   • r = sr, c = sc
   • visited[r][c] = True
   • answer = 1
6. Для каждой команды:
   • сначала считаем предполагаемую новую позицию nr, nc;
   • если она внутри границ и не содержит '#', то обновляем r, c;
   • если клетка r, c ещё не посещалась, отмечаем её и увеличиваем answer.
7. Выводим answer.

4. Почему это работает

Докажем, что алгоритм считает правильный ответ.

После чтения входных данных:

• поле хранится корректно;
• стартовая позиция робота известна;
• клетка старта считается свободной, что соответствует условию.

Далее мы обрабатываем команды строго в том порядке, в котором они заданы.

Для каждой команды алгоритм делает ровно то, что написано в условии:

• определяет соседнюю клетку в нужном направлении;
• если переход возможен, перемещает робота;
• если переход невозможен, оставляет робота на месте.

Значит, после обработки каждой команды позиция (r, c) совпадает с реальной позицией робота.

Теперь про посещённые клетки:

• стартовая клетка отмечается посещённой сразу;
• после каждой команды отмечается та клетка, в которой робот фактически оказался;
• если клетка уже была отмечена раньше, ответ не увеличивается;
• если клетка новая, ответ увеличивается на 1.

Следовательно, в answer в конце окажется ровно количество различных клеток, которые робот посетил за всё время работы.

5. Сложность

Пусть всего n * m клеток, а команд k.

Время

• чтение поля: O(n * m)
• обработка команд: O(k)

Итого: O(n * m + k)

Память

• хранение поля: O(n * m)
• массив visited: O(n * m)

Итого: O(n * m)

6. Код на C++17

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    vector<string> grid(n);
    int sr = -1, sc = -1;

    for (int i = 0; i < n; i++) {
        cin >> grid[i];
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '@') {
                sr = i;
                sc = j;
                grid[i][j] = '.';
            }
        }
    }

    string s;
    cin >> s;

    vector<vector<bool>> visited(n, vector<bool>(m, false));
    int r = sr, c = sc;
    visited[r][c] = true;
    int answer = 1;

    for (char ch : s) {
        int nr = r, nc = c;
        if (ch == 'U') nr--;
        else if (ch == 'D') nr++;
        else if (ch == 'L') nc--;
        else if (ch == 'R') nc++;

        if (nr >= 0 && nr < n && nc >= 0 && nc < m && grid[nr][nc] != '#') {
            r = nr;
            c = nc;
        }

        if (!visited[r][c]) {
            visited[r][c] = true;
            answer++;
        }
    }

    cout << answer << "\n";
    return 0;
}

7. Код на Python 3

n, m, k = map(int, input().split())

grid = []
sr = -1
sc = -1

for i in range(n):
    row = list(input())
    for j in range(m):
        if row[j] == '@':
            sr = i
            sc = j
            row[j] = '.'
    grid.append(row)

commands = input()

visited = [[False] * m for _ in range(n)]
r, c = sr, sc
visited[r][c] = True
answer = 1

for ch in commands:
    nr, nc = r, c
    if ch == 'U':
        nr -= 1
    elif ch == 'D':
        nr += 1
    elif ch == 'L':
        nc -= 1
    else:
        nc += 1

    if 0 <= nr < n and 0 <= nc < m and grid[nr][nc] != '#':
        r, c = nr, nc

    if not visited[r][c]:
        visited[r][c] = True
        answer += 1

print(answer)