| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 13 | 6 | 5 | 45.455% |
Robotų varžyboms sukonstruota T skirtingo dydžio stačiakampių trasų-labirintų, padalintų į vienetinius kvadratėlius. Ant kai kurių kvadratėlių priklijuotos kvadratėlio dydžio plytelės (sienos) ir šiais kvadratėliais robotai judėti ar ant jų stovėti negali.
Varžybose dalyvauja kvadrato formos robotai galintys judėti tik keturiomis kryptimis lygiagrečiai trasos kraštinėms. Vieno varžybų etapo metu robotas pastatomas starto juostoje iš kairės, jis turi užvažiuoti ant tam etapui numatytos trasos iš kairiojo krašto, pervažiuoti labirintą (nebūtinai trumpiausiu keliu) ir išvažiavęs pro dešinįjį kraštą pasiekti finišo juostą.
Etapą laimi dalyvis, kurio užduotį įveikęs robotas yra didžiausias (t. y. kurio kvadrato formos roboto kraštinė bus ilgiausia).
Varžybų organizatoriai nori prieš pat varžybas patikrinti trasas ir sužinoti, kokio dydžio robotai turės būti konstruojami varžyboms. Parašykite programą, kuri žinodama kiekvienos trasos planą, apskaičiuotų koks turėtų būti didžiausias galimas roboto kraštinės ilgis tai trasai.
Pirmoje eilutėje pateiktas trasų skaičius T.
Toliau pateikti T trasų duomenys: i-ąįą trasą aprašančioje pirmoje eilutėje pateiktas jos plotis ni ir ilgis mi . Tolesnėse ni eilučių pateikiama po mi simbolių, aprašančių i-ąją trasą:
Visų trasų viršutinę ir apatinę eiles sudaro tik užimti langeliai.
Išveskite T eilučių, kuriose būtų po vieną sveikąjį skaičių: i-ojoje eilutėje išveskite didžiausią kvadrato kraštinės ilgį ai , tokį, kad šio dydžio robotas galėtų įveikti i-ąją trasą.
1 8 8 ######## ##...#.. #......# #....... ....#... ........ ......## ########
2
2 × 2 roboto judėjimo pavyzdys:
Didesni robotai šios trasos neįveiks.
4 9 9 ######### #..#..#.# .....##.. ......... ......... ......... #.#....#. ....##... ######### 7 10 ########## .......### ....##..## .###...### ##...####. ##........ ########## 6 2 ## .. .. .. .. ## 5 6 ###### #...#. ..##.. ..#..# ######
3 1 4 0
Robotų judėjimas pirmose dvejose testo trasose:
Robotai neprivalo būti visiškai įvažiavę į trasą, todėl trečiai trasai 4 × 4 robotas tenkina sąlygą ir yra didžiausias robotas, galintis įveikti šią trasą.
Deja, paskutinė trasa sukonstruota netinkamai. Kadangi robotai negali judėti įstrižai, ketvirtosios trasos nepavyks įveikti jokiam robotui.