АЛГОРИТМЫН ЦАГААН ТОЛГОЙ

Бомберман тэгш өнцөгт хэлбэртэй торонд амьдардаг. Торны зарим нүд бөмбөгтэй, зарим нүд хоосон байгаа.

Тоглолтын эхэнд тэсрэх бөмбөг бүрийг торны дурын нүдэнд байрлуулж болно. Гэхдээ нэгэнт байрлуулсан бөмбөг яг 3 секундын дараа дэлбэрнэ.

Тэсрэх бөмбөг дэлбэрэхэд тухайн бөмбөг устаж, тухайн нүд болон хөрш талуудтай зэргэлдээх дөрвөн нүд ч мөн хоосон болно.

Өөрөөр хэлбэл бөмбөг дэлбэрвэл тухайн нүд болон хөрш нүднүүд цэвэрлэгдэнэ гэсэн үг.

Хэрэв хөрш зэргэлдээх нүдэнд тэсрэх бөмбөг байгаа бол хөрш зэргэлдээ бөмбөг тэсрэхгүйгээр устдаг тул цааш гинжин урвал мэтээр үргэлжлэхгүй.

Бомберман нь тэсрэх бөмбөгний хамгаалалттай тул тэгш өнцөгтийн нүднүүдээр чөлөөтэй хөдөлж чаддаг.

Түүний хийж байгаа зүйл нь:

1. Эхний удаад Бомберман торны анхы төлөв байдалд өөрийн хүссэн нүднүүдэд тэсрэх бөмбөг байрлуулдаг.

2. Дараагийн секундэд Бомберман юу ч хийдэггүй.

3. Түүний дараагийн секундэд Бомберман бүх тэсрэх бөмбөггүй нүднүүдэд тэсрэх бөмбөг байрлуулдаг бөгөөд ингэснээр бүх тэгш өнцөгтийн бүх нүднүүд бөмбөгөөр дүүргэгддэг. Одоогоор ямар ч бөмбөг дэлбэрээгүй байна.

4. Дахин нэг секундын дараа яг гурван секундын өмнө суулгасан аливаа бөмбөг дэлбэрэх болно. Ингээд Бомберман тэгш өнцөгтөө эргэн авч үзнэ. Тэгээд Бомберман 3 ба 4-р алхамуудыг тодорхойгүй удаа давтана. Бомберманы ижил хугацаанд суурилуулсан тэсрэх бөмбөгнүүд нэгэн зэрэг дэлбэрэхийг анхаарна уу.

Бомберманы эхний удаад байрлуулсан тэсрэх бөмбөг бүхий тэгш өнцөгтийн төлөв байдал өгөгдсөн бол өгөгдсөн секундын дараа тэгш өнцөгтийн нүднүүдийн төлөв байдлыг тодорхойлно уу.

Жишээлбэл:

Хэрэв тэгш өнцөгт торны эхний төлөв байдал дараах байдалтай байгаа бол:

…

.О.

…

эхний секундын дараа тэгш өнцөгтийн төлөв байдал өөрчлөлтгүй анхны төлөв байдалтайгаа ижилхэн харагдана.

Хоёр дахь секундын дараа Бомберман бүх хоосон нүднүүдийг бөмбөгөөр дүүргэнэ.

ООО

ООО

ООО

Гурав дахь секундэд 3 секунтын өмнө суулгасан бөмбөгнүүд дэлбэрч, тухайн нүднүүдээ болон хөрш нүднүүдээ хоосолно.

…

…

…

Функцийн тодорхойлолт:

Доорх редактор дээр bomberMan функцийг гүйцэтгэнэ үү.

Энэ нь тэгш өнцөгт торны эцсийн төлвийг илэрхийлж буй массив мөрийг буцаана.

BomberMan функц дараахь параметр (ууд) -тай байна.

n: бүхэл тоо,  секундын тоо:

grid: Тэгш өнцөгт торны анхны төлөв байдлыг илэрхийлсэн хүснэгт

Оролтын формат

Эхний мөрөнд зайгаар тусгаарлагдсан r,c,n гэсэн 3 бүхэл тоо өгөгдөнө. Эдгээр нь харгалзан  хүснэгтийн  мөр, багана, секундын тоог илэрхийлнэ. Дараагийн r ширхэг мөр бүрт тухайн дугаар бүхий мөрөнд тэсрэх бөмбөг байгаа эсэхийг илэрхийлэх тэмдэгтүүд байна. Цэг (.) тэмдэгт нь хоосон нүдийг илэрхийлэх ба O тэмдэгт (ascii 79) нь тэсрэх бөмбөг байгааг илэрхийлнэ.

Хязгаарлалт:

1<= r, c <=200

1<=n<=10^9

Дэд бодлого: 

1<=n<=200 тохиолдолд бодвол нийт даалгаврын 40 хувь хүртэлх оноог авч болно.

Гаралтын формат:

Тэгш өнцөгтийн эцсийн төлвийг хэвлэнэ. /n секундын дараах/

Жишээ

Оролт

6 7 3

.......

...O...

....O..

.......

OO.....

OO.....

Гаралт

OOO.OOO

OO...OO

OOO...O

..OO.OO

...OOOO

...OOOO

Тайлбар

Тэгш өнцөгт эхний төлөвтөө:

.......

...O...

....O..

.......

OO.....

OO.....

Bomberman эхний секундэд юу ч хийхгүй тул өөрчлөлт гарахгүй.

Тиймээс нэг секундын дараа

.......

...O...

....O..

.......

OO.....

OO.....

Хоёр дахь секундэд Bomberman бүх хоосон нүднүүдийг тэсрэх бөмбөгөөр дүүргэнэ.

Тиймээс 2 секундын дараах хүснэгтийн төлөв байдал дараах байдалтай байна:

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

OOOOOOO

Гурав дахь секундэд, Bomberman 3 секундын өмнө суулгасан бүх бөмбөгнүүдээ дэлбэлдэг.

Ингээд 3 секундын дараах байдлаар хүснэгт дараах хэлбэртэй болно:

OOO.OOO

OO...OO

OOO...O

..OO.OO

...OOOO

...OOOO

Орчуулсан : Хөвсгөл аймгийн Ирээдүй сургуулийн багш Д.Батмөнх