Структури даних. Черга

Черга у Python реалізується у вигляді списку, до якого додаються елементи командою append, і видаляються з голови черги командою pop(0).
pop(0)чергаappend


Задача 1. Дано малюнок у вигляді матриці. Потрібно перефарбувати одноколірну область координат x,y на колір 2.

У вхідному файлі дано вміст колірної матриці. Наприклад:

0 1 0 1 1
1 1 1 2 2
0 1 0 2 2
3 3 1 2 2
0 1 1 0 0

картинка

Вихідні дані: кількість клітинок, у котрих змінився колір та новий вміст матриці.
5
0 2 0 1 1
2 2 2 2 2
0 2 0 2 2
3 3 1 2 2
0 1 1 0 0

У цій та наступній задачах потрібно використовувати матрицю - двовимірну таблицю. Це можна реалізувати за допомогою двовимірного списку. 

Припустимо, що вміст цієї таблиці міститься у файлі. У такому разі наступні команди дозволяють відкрити файл та зчитати його вміст у двовимірний список

text=open('file.txt','r')
board = []
n=int(text.readline())
for ryadok in text.readlines():
    board.append(ryadok.split())

split() перетворює вміст зчитаного текстового рядка на список, розділюючи елементи за пробілами

Для переведення вмісту таблиці з символів у числа можна скористатись наступними командами:

for i in range(n):
    for j in range(n):
        board[i][j]=int(board[i][j]) 

Для виведення списку у вигляді рядків та стовпців таблиці можна скористатись наступними командами:

for i in range(n):
    print()
    for j in range(n):
        print(board[i][j], end=" ")

Розглянемо алгоритм роботи з чергою для цієї задачі. У чергу заносяться координати першої клітинки (з вхідних даних). У змінну base_color записується базовий колір цієї точки, щоб зафіксувати той колір, котрий потрібно змінювати.

Координати x,y початової точки, та новий колір new_color вводяться з клавіатури (або як аргументи командного рядка).

Поки черга не порожня (її довжина більша нуля), потрібно брати елементи з черги (два елементи, як координати точки), і якщо колір точки рівний базовому, то колір цієї точки змінюється на новий (з вхідних даних), а в чергу заносяться 4 сусідні точки по горизонталі та вертикалі. Перед записом у чергу потрібно перевіряти, чи сусідня точка (координати якої відрізняються  від поточних на 1), розміщена у межах матриці. Ці дії повторюються поки черга не вичерпається.

Задача 2. Визначити, чи може потрапити шаховий кінь з однієї клітинки шахової дошки в іншу

кінь

Створимо список усіх клітинок шахової дошки board у вигляді двовимірного списку і заповнимо усі клітинки нулями. Переглянуту клітинку позначатимемо 1, занесені у чергу перегляду клітинки позначатимемо 2.

Розпочавши із клітинки, вказаної користувачем, будемо заносити у чергу places всі клітинки, у які може потрапити кінь із даної.

Поки у черзі є елементи, беремо із цієї черги два елементи, друкуємо їх та перетворюємо на числа (для виконання подальших операцій). Змінюємо статус клітинки на позначений (значення стає 2).

Переглядаємо список можливих ходів коня (цей список міститься у змінній moves), і якщо потенційні нові координати na та nb потрапляють всередину шахової дошки, додаємо ці координати у чергу перегляду клітинок.

Задача 3. Порахувати, за скільки ходів всі клітинки виявились у черзі

Задача 4. Визначити найбільшу довжину черги

Задача 5. У колі стоять N людей. Вони грають у лічилку, за якою з кола виходить кожен K. Надрукувати порядок виходу з черги

кішки-мишки


Остання зміна: п'ятниця 4 жовтня 2019 11:57