k и два списка правил. Правило [a, b] из row_rules значит, что число a должно стоять в строке строго выше числа b. Правило [a, b] из col_rules значит, что a должно стоять в столбце строго левее b. Все числа в правилах — от 1 до k.
Постройте таблицу k × k, в которой каждое число от 1 до k встречается ровно один раз, остальные клетки равны 0, и все правила выполнены.
Чтобы ответ был однозначным, номера строк выдаются так:
1. Сначала в очередь по возрастанию встают все числа, которые ни в одном правиле не стоят на месте b.
2. Пока очередь не пуста, берём число из её начала и отдаём ему следующую свободную строку сверху (0, 1, 2, …).
3. Затем проходим по правилам row_rules, в которых это число стоит на месте a, в том порядке, в каком они записаны, и вычёркиваем их. Как только у числа b не осталось невычеркнутых правил, где оно на месте b, оно встаёт в конец очереди.
Номера столбцов выдаются точно так же по col_rules. Если в строках или в столбцах место получили не все k чисел, правила противоречат друг другу — верните пустой список.k=3, row_rules=[[2, 1], [3, 1]], col_rules=[[1, 3], [3, 2]] → [[0, 0, 2], [0, 3, 0], [1, 0, 0]]
Строки: вначале свободны 2 и 3, они получают строки 0 и 1, а 1 — строку 2. Столбцы: свободна только 1 (столбец 0), за ней 3 (столбец 1), затем 2 (столбец 2).
k=2, row_rules=[[1, 2]], col_rules=[[1, 2], [2, 1]] → []
По столбцам 1 должна быть левее 2, а 2 левее 1 — противоречие, поэтому ответ пустой.
k=4, row_rules=[[4, 2], [4, 1]], col_rules=[[3, 1]] → [[0, 3, 0, 0], [0, 0, 4, 0], [2, 0, 0, 0], [0, 0, 0, 1]]
k ≤ 400len(row_rules), len(col_rules) ≤ 10⁴a, b ≤ k, a ≠ bk=3, row_rules=[[2, 1], [3, 1]], col_rules=[[1, 3], [3, 2]]
[[0, 0, 2], [0, 3, 0], [1, 0, 0]]
«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 86 тестов на сервере, включая скрытые.