Question

ИВТ/ 9 КЛАСС/ ХЕЕЕЛП/ 30 БАЛЛОВ Лабиринт Терминатор T101 заблудился в лабиринтах подвальных помещений компании Cyberdyne Systems. Подвал представляет собой прямоугольную площадку размена NxM клеток. Каждая клетка может быть проходимой, а может быть непроходимой. У терминатора есть план подвала, в котором проходимые клетки отмечены точками (“.”), непроходимые –иксами (символ “x”), текущее положение терминатора отмечено символом “+”. Чтобы организовать поиски выхода, терминатор должен отметить на своем плане все проходимые клетки, в которые он может попасть и подсчитать их количество (включая клетку, на которой он находится в данный момент). Он может ходить только по проходимым клеткам, совершая каждый переход на одну клетку вверх, вниз, вправо или влево. При этом он не может выходить за границы заданного прямоугольника. Входные данные В первой строке входного файла задается через пробел два числа N и M — размеры подвала, причем 1 ≤ N ≤ 100, 1 ≤ M ≤ 100. В последующих N строках вводится план лабиринта — по M символов в строке. Выходные данные В выходной файл выведите единственное число — количество достижимых терминатором клеток. Пример входного файла 4 6 .x.x.. .xxx.. ....xx x.+.x. Пример выходного файла 9

Answer 1

Const
    max_length = 10;

type
    arr = array [0..max_length, 0..max_length] of byte;

var
    a: arr;
    i, j, n, m, k, x, y: byte;
    c: char;
    f: text;

//procedure PrintMatrix(a: arr);
//begin
//    for var i := 0 to max_length do
//    begin
//        writeln;
//        for var j := 0 to max_length do
//            write(a[i, j], ' ');
//    end;
//    writeln;
//end;

procedure labirint(i, j: byte);
begin
    if (i <= n) and (i >= 0) and (j <= m) and (j >= 0) and (a[i, j] = 0) then begin
        a[i, j] := 1;
        k := k + 1;
        labirint(i, j - 1);
        labirint(i, j + 1);
        labirint(i - 1, j);
        labirint(i + 1, j);
    end;
end;

begin
    Assign(f, 'input.txt');
    Reset(f);
    
    readln(f, n, m);
    for i := 0 to n do
    begin
        for j := 0 to m do
        begin
            read(f, c);
            case c of
                'x': a[i, j] := 2;
                '.': a[i, j] := 0;
                '+':
                    begin
                        x := i;
                        y := j;
                        a[i, j] := 0;
                    end;
            end;
        end;
        readln(f);
    end;
    Close(f);
    
//    PrintMatrix(a);
    
    labirint(x, y);
    writeln(k);
//    PrintMatrix(a);
end.

Answer 2

Для решения данной задачи можно использовать поиск в ширину (BFS) или поиск в глубину (DFS).

Вариант решения с использованием поиска в ширину:

1. Считываем размеры подвала N и M. 2. Создаем двумерный массив размером N x M для хранения плана лабиринта. 3. Считываем план лабиринта и заполняем массив. 4. Создаем двумерный массив посещенных клеток размером N x M и инициализируем его значением false. 5. Создаем очередь для хранения координат клеток, которые нужно посетить. 6. Ищем текущую позицию терминатора в массиве и добавляем ее в очередь. 7. Пока очередь не пуста, выполняем следующие шаги: - Извлекаем из очереди следующую клетку. - Если клетка уже посещена, пропускаем ее. - Если клетка проходима, отмечаем ее как посещенную и добавляем соседние клетки, которые еще не посещены, в очередь. 8. Подсчитываем количество посещенных клеток. 9. Выводим количество посещенных клеток.

Пример реализации на языке Python:

from collections import deque

# Считываем размеры подвала
N, M = map(int, input().split())

# Создаем двумерный массив для плана лабиринта
labyrinth = [input() for _ in range(N)]

# Создаем двумерный массив посещенных клеток
visited = [[False] * M for _ in range(N)]

# Создаем очередь для хранения координат клеток
queue = deque()

# Ищем текущую позицию терминатора и добавляем ее в очередь
for i in range(N):
    for j in range(M):
        if labyrinth[i][j] == '+':
            queue.append((i, j))
            visited[i][j] = True

# Инициализируем счетчик посещенных клеток
count = 0

# Выполняем поиск в ширину
while queue:
    x, y = queue.popleft()
    count += 1

# Проверяем соседние клетки
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx, ny = x + dx, y + dy

# Проверяем, что клетка находится в пределах подвала
        if 0 <= nx < N and 0 <= ny < M:
            # Проверяем, что клетка проходима и еще не посещена
            if labyrinth[nx][ny] == '.' and not visited[nx][ny]:
                queue.append((nx, ny))
                visited[nx][ny] = True

# Выводим количество посещенных клеток
print(count)

Пример работы программы: Входные данные: ``` 4 6 .x.x.. .xxx.. ....xx x.+.x ``` Выходные данные: ``` 9 ``` В данном примере терминатор может достичь 9 проходимых клеток, включая клетку, на которой он находится в данный момент.