시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB0000.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.

제한

  • 3 ≤ N, M ≤ 300

서브태스크

번호배점제한
117

N = 3

255

N, M ≤ 40

328

Užimtų nekraštinių1 langelių bus daugiausiai 300.

1Langelių, kurie nėra pirmoje arba paskutinėje eilutėje, arba pirmame ar paskutiniame stulpelyje.

예제 입력 1

5 6
######
###..#
#...##
#.##.#
######

예제 출력 1

4

Vienas galimų roboto kelių atrodo taip:

  • iš (4; 2) nuvažiuos viršun į (3; 2);
  • toliau važiuoti viršun nebegalės, todėl pasuks dešinėn;
  • ir važiuos į langelius (3; 3), (3; 4);
  • vėl atsitrenkęs į sieną pasisuks apačion;
  • tačiau ir ten yra siena, tad toliau besisukant nukryps kairėn;
  • ir važiuos atgal į langelius (3; 3), (3; 2);
  • pasiekęs sieną vėl suksis ir taip toliau važinės pirmyn atgal, jokio papildomo ploto nebeišsiurbdamas.

Iš viso bus išsiurbti 4 langeliai, čia pažymėti skaičiais jų pirmo išsiurbimo tvarka:

######
###..#
#234#
#1##.#
######

채점 및 기타 정보

  • 예제는 채점하지 않는다.