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

Черга у 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), розміщена у межах матриці. Ці дії повторюються поки черга не вичерпається.

cherga=[]
cherga.append((x,y))
base_color=board[x][y]
while len(cherga) > 0:
    a,b=cherga.pop(0)
    if board[a][b]==base_color:
        board[a][b]=new_color
        if a > 0:
            cherga.append(((a-1),b))
        if a < n-1:
            cherga.append(((a+1),b))
        if b > 0:
            cherga.append((a,(b-1)))
        if b < n-1:
            cherga.append((a,(b+1)))

Показати фрагмент коду

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

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

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

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

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

board = []
for i in range(8):
    board.append([0] * 8)

moves=[[-2,-1],[-2,1],[-1,-2],[-1,2],[1,-2],[1,2],[2,-1],[2,1]]

places=[]

k=input().split()
places.append( k )

while len(places)>0:
    a,b=places.pop(0)
    print(a,b)
    a=int(a)
    b=int(b)
    board[a][b]=2
    for i in range(8):
        na=a+moves[i][0]
        nb=b+moves[i][1]
        if ((na>=0) and (na<=7) and (nb>=0) and (nb<=7)):
            if (board[na][nb]==0):
                if (na,nb) not in places:
                    places.append((na,nb))
                    board[na][nb]=1

Показати програму

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

Необхідно перевіряти список дошки board. Якщо не залишилось нулів - значить всі клітинки або відвідані, або вже у черзі. Ймовірно для цього варто створити функцію

Показати алгоритм

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

Використати функцію len() та змінну, котра зберігатиме поточний максимальний розмір черги

Показати алгоритм

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

У цій задачі слід переписувати елементи з початку (pop(0)) черги в її кінець (append), "пропускаючи" гравців, і видаляти гравця з останньої позиції в черзі (pop).

Показати підказку