eolymp
bolt
Try our new interface for solving problems
Məsələlər

E. Труби

E. Труби

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
e.gif

Козак Вус захотiв стати президентом Потоколяндiї, а для цього, як водиться, потрiбно зробити якусь добру справу для добрих громадян, щоб вони стали ще добрiшими, а козак Вус — популярнiшим серед народу. Отож вiн вирiшив вiдремонтувати водопровiдну систему країни. Вона знаходиться пiд землею, i для простоти вона роздiлена на однаковi квадратнi фрагменти так, що має вигляд поля n * m. Фрагменти нумеруються зверху вниз вiд 1 до n та злiва направо вiд 1 до m. Кожен фрагмент може бути або порожнiм (позначається символом 0), або в ньому можезнаходитись труба одного з 6 типiв:Водопровiд називається замкненим, якщо для кожної труби кожен її кiнець з’єднаний з кiнцем якоїсь iншої труби.Нещодавно вас призначили заступником Козака Вуса з питань водопроводу, тож тепер ви можете повернути будь-яку трубу на кут, кратний 90◦. Ваше завдання — за допомогою поворотiв зробити цей водопровiд замкненим або повiдомити, що це неможливо.

Giriş verilənləri

Перший рядок мiстить три цiлi числа n, m та g (1 ⩽ n;m ⩽ 400, 0 ⩽ g ⩽ 8) — довжина та ширинаполя, а також номер групи вiдповiдно.

Кожний з наступних n рядкiв мiстить по m цiлих чисел a[i]; 1; a[i]; 2; : : : ; a[i];m (0 ⩽ a[i];j ⩽ 6)—число, що описує тип труби, розташованої в клiтинцi з координатами (i; j).

Çıxış verilənləri

Виведiть NO, якщо труби неможливо повернути так, щоб утворити замкнену систему, у протилежному випадку виведiть YES, а далi виведiть n рядкiв по m чисел у кожному—опис замкненої системи, утвореної поворотами, у форматi, описаному вище.

####Примiтка

e1.gif

Iлюстрацiя до тестових прикладiв: початковий та замкнений (якщо вiн iснує) стан:

Оцiнювання

  1. (7 балiв) 1 ⩽ n;m ⩽ 3;

  2. (9 балiв) 1 ⩽ n;m ⩽ 400; до 4 кутових труб;

  3. (12 балiв) 1 ⩽ n;m ⩽ 400; до 8 кутових труб;

  4. (13 балiв) 1 ⩽ n ⩽ 400; m = 2;

  5. (13 балiв) 1 ⩽ n;m ⩽ 400; якщо розв’язок iснує, то в хоча б одному з них кожен замкнений контур складається з

4 кутових труб i довiльної кiлькостi прямих труб;

  1. (14 балiв) 1 ⩽ n ⩽ 400; m = 4;

  2. (15 балiв) 1 ⩽ n;m ⩽ 50;

  3. (17 балiв) без додаткових обмежень.

Nümunə

Giriş verilənləri #1
5 5 0
0 0 0 0 0
0 3 1 2 4
0 2 0 0 1
0 1 0 0 1
0 6 2 2 5
Çıxış verilənləri #1
YES
0 0 0 0 0 
0 5 1 1 6 
0 2 0 0 2 
0 2 0 0 2 
0 4 1 1 3 
Giriş verilənləri #2
3 2 0
0 0
1 2
3 0
Çıxış verilənləri #2
NO
Giriş verilənləri #3
8 8 0
0 4 2 1 2 2 3 0
0 2 5 4 0 0 1 0
0 1 4 5 0 0 1 0
0 1 0 0 3 2 5 0
0 2 5 3 4 2 1 5
0 1 2 5 5 0 0 1
0 2 5 2 5 0 0 1
0 4 2 1 2 2 2 5
Çıxış verilənləri #3
YES
0 5 1 1 1 1 6 0 
0 2 5 6 0 0 2 0 
0 2 4 3 0 0 2 0 
0 2 0 0 5 1 3 0 
0 2 5 6 4 1 1 6 
0 2 2 4 6 0 0 2 
0 2 4 1 3 0 0 2 
0 4 1 1 1 1 1 3 
Mənbə XXXII Всеукраїнська олiмпiада з iнформатики, Одеса, 25-29 березня 2019 року