CaveExploration

Personajul principal din nuvela "La Țigănci", Omeskoku, este blocat într-o peșteră monstroasă (chiar sunt monștri în peșteră!). El are acces la un satelit care îi poate da harta peșterii. Peștera e sub forma unui labirint. Peștera este monstroasă, astfel, în unele zone din peșteră sa află câte un monstru.

Monștrii sunt destul de prietenoși, totusi, astfel Omeskok se joacă un joc cu ei. La fiecare pas Omeskok și monștrii pot alege dacă să se miște sau să rămână pe loc, iar toate mișcările se fac simultan. Monștrii, precum și Omeskok, dacă aleg să se miște, aceștia se pot mișca o unitate în fiecare dintre cele 4 direcții cardinale (Nord, Est, Sud, Vest). Jocul are totusi o miza: Dacă monștrii reușesc să îl prindă pe Omeskok, acestia vor mânca bine :).

Dacă Omeskok reușeste să se salveze și să iasă din matrice acesta câștigă dreptul la viață iar monștrii vor muri de foame. Omeskok observă totuși numărul imens de monștri care se află în peșteră, astfel este foarte puțin probabil să poată scăpa. Satelitul lui foarte performant poate să lanseze și lasere cu care poate neutraliza monștrii, însă acesta vrea să neutralizeze cât mai puțini, pentru ca ei să nu se prindă (daca se prind, nu mai vor să se joace și il pot mânca pe Omeskok foarte ușor).

Cerință

Care este numărul minim de monștri care trebuie neutralizați?

Date de intrare

Se vor citi valorile $n$ si $m$ reprezentând mărimea peșterii. Peștera va fi citită sub forma unei matrici de $n$ linii și $m$ coloane.
Componentele peșterii vor fi reprezentate de următoarele simboluri:

• # reprezintă un obstacol peste care nici monștrii, nici Omeskok nu poate trece;
• . reprezintă o parcelă accesibilă atât de monștrii, cât și de Omeskok;
• M reprezintă un monstru.

Date de ieșire

Se va afișa un singur număr reprezentând numărul minim de monștri care trebuie eliminați astfel încât Omeskok să poată ajunge la ieșire.

Restricții și precizări

• $1 \le n,m \le 1000$
• Omeskok va începe mereu din colțul stânga sus al matricii iar ieșirea din peșteră va fi tot timpul în colțul dreapta jos al peșterii;
• Porțiunea dată de peșteră este înconjurată cu obstacole (nu poți ieși din terenul dat);
• Dacă Omeskok nu poate evada din peșteră dar nici monștrii nu pot să îl prinda fără să îl lase sa evadeze, atunci aceasta este considerată o victorie pentru monștri, deoarece scopul lui Omeskok nu este să nu fie mâncat, ci să evadeze fără sa fie mâncat!
• Omeskok va avea mereu cel puțin o rută prin care poate evada;
• Pot să fie mai mulți monștri pe aceeași parcelă, dar inițial va fi doar unul;
• Omeskok este mâncat dacă va ajunge pe aceeași parcelă cu un monstru;
• Dacă Omeskok ajunge pe ieșire în același timp cu un montru, el tot va fi mâncat deoarece durează până se urcă pe scară;
• Monștrii joacă optim;
• Matricea poate conține și alte caratere, dar vor fi considerate porțiuni libere ornamentate.

Exemplul 1

stdin

5 5
...M.
.###.
M..#.
.....
...#.

stdout

2

Exemplul 2

stdin

6 6
......
.##.#.
....#.
M#M.#.
.####.
.#....

stdout

0