Breakout
Турнир за Купата на Декана, 2015
Time Limit: 0.1s, Memory Limit: 64MiB
Ели беше отвлечена! За щастие, тя намери плана на имението, в което бива държана като заложник. За нещастие, тя не знае къде точно в него се намира, тъй като беше със завързани очи, докато я вкарваха вътре.

За простота ще считаме имението като матрица с N реда и M колони. Всяка клетка може или да бъде празна (коридор) или блокирана (стена). В началото Ели се намира в някоя от празните клетки, но не знаем в коя от тях точно.

Ели може да се движи в четирите основни посоки – наляво, надясно, нагоре и надолу. Придвижването в съседна празна клетка не отнема време (все пак, трябва просто да се направят няколко крачки). Придвижването в блокирана клетка, обаче, отнема малко повече време – тя първо трябва да разбие стената там. Това отнема по един час на клетка. Считаме, че момичето е избягало от имението, когато достигне до неговия край – тоест до която и да е от крайните клетки на матрицата.

Ели вярва, че е затворена в някоя от празните клетки, от която ще ѝ отнеме най-много възможно време за да избяга. Тя ви е дала карта на имението под формата на матрица с N реда и M колони, всяка клетка от която е или '.' (коридор) или '#' (стена). Помогнете ѝ, като намерите броя на клетките, в които има възможност да се намира тя.
Вход
На първия ред на стандартния вход ще съдържа две цели числа N и M – съответно броя редове и броя колони на картата. Следват N реда, всеки съдържащ по M символа от азбуката {'.', '#'}.
Изход
На стандартния изход изведете едно цяло число – броя клетки, от които би се излязло с най-много време дори при избор на оптималния път.
Ограничения
  • 1 ≤ N, M ≤ 1,000
Примерен Вход Примерен Изход
7 14 .#............ .######....... .#.##.##...... .##..#.#...... .#.###.#.####. .#...###.#.##. ..####...###.. 2
5 12 #.#.#.#.#.#. .#.#.#.#.#.# #.#.#.#.#.#. .#.#.#.#.#.# #.#.#.#.#.#. 15
В първия пример има три "стаи", като една от тях се намира във вътрешността на друга. За да избяга от там, на момичето ще са нужни два часа. Въпросната "вътрешна" стая съдържа две празни клетки.
Мрън!