| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 0 | 0 | 0 | 0.000% |
Romas nemėgsta siurbti dulkių, todėl įsigijo robotą-dulkių siurblį. Deja, robotas pasirodė esąs primityvus – jis siurbdamas dulkes tiesiog važiuoja į priekį, kol atsitrenkia į kliūtį (pavyzdžiui, baldą ar sieną), tada pasisuka 90 laipsnių į dešinę ir vėl kartoja tą patį.
Romo buto planas pavaizduotas N × M matmenų tinkleliu. Plane kiekvienas langelis yra arba laisvas (kur robotas gali siurbti), arba užimtas (kliūtis). Robotas juda langeliais lygiagrečiai tinklelio kraštinėms.
Ryte išeidamas Romas įjungs robotą ir nori, kad jam grįžus kuo didesnis plotas būtų išsiurbtas.
Raskite, kokį didžiausią plotą robotas gali išsiurbti, jeigu robotą galima paleisti iš bet kurio laisvo langelio į viršų, į apačią, į kairę arba į dešinę.
Pirmoje eilutėje pateikiami du sveikieji skaičiai: stačiakampio kambario plano matmenys N ir M. Tolesnėse N eilučių yra po M simbolių, nusakančių kambario planą. Kiekvienas simbolis nurodo langelio būseną:
. (taškas) – laisvas langelis;# (grotelės) – užimtas langelis.Visi kraštiniai langeliai yra užimti. Visuomet bus bent vienas laisvas langelis.
Išveskite vieną sveikąjį skaičių – kiek daugiausiai langelių robotas gali išsiurbti.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 17 | N = 3 |
| 2 | 55 | N, M ≤ 40 |
| 3 | 28 | Užimtų nekraštinių1 langelių bus daugiausiai 300. |
1Langelių, kurie nėra pirmoje arba paskutinėje eilutėje, arba pirmame ar paskutiniame stulpelyje.
5 6 ###### ###..# #...## #.##.# ######
4
Vienas galimų roboto kelių atrodo taip:
Iš viso bus išsiurbti 4 langeliai, čia pažymėti skaičiais jų pirmo išsiurbimo tvarka:
###### ###..# #234# #1##.# ######
Olympiad > Lithuanian Olympiad in Informatics > Lithuanian Olympiad in Informatics 2015/2016 > National Round (2) > 7-9 Classes 2번