Problema Pampas

Pampasul este o largă regiune vastă din Argentina, întinzându-se la sud de Buenos Aires și fiind caracterizată prin vaste câmpii brăzdate de lacuri, precum și de foarte abundente ploi in sezonul umed. Gigel experimentează viața de Gaucho (versiunea argentiniană de cowboy) dar fiind începător, a fost prins pe picior greșit de ploaie. Harta regiunii este reprezentată sub forma unei matrici în care valorile de 0 reprezintă pământ uscat, iar valorile de 1 reprezintă lacuri. Ploaia fiind abundentă, lacurile se extind cu rapiditate, acoperind în fiecare oră toate zonele de pământ adiacente zonelor de apă. Inițial Gigel se află într-o poziție cu pământ, marcata cu litera G, iar scopul său este să ajungă într-o altă poziție de pământ marcată cu S, reprezentând satul cel mai apropiat și care este ferit de inundații.

Cerință

Determinați numărul maxim de ore pe care Gigel le poate petrece zăbovind în ploaie, astfel încât atunci când va pleca să poată ajunge în sat.

Date de intrare

Fişierul de intrare pampas.in conţine, pe prima linie numerele naturale n și m, reprezentând dimensiunile regiunii. Următoarele n linii vor conține câte n caractere, din mulțimea {0,1,G,S} reprezentând descrierea regiunii.

Date de ieșire

Fișierul pampas.out va conține o singură valoare naturală, reprezentând răspunsul la cerință.

Restricții și precizări

• n≤200, m≤2000;
• pozițiile la care se află Gigel și Satul sunt considerate poziții de uscat și nu pot fi inundate;
• pentru teste în valoare de 30%: n,m ≤ 50;
• se garantează că pe configurația inițială a zonei Gigel poate ajunge în sat;
• configurația inițială a terenului este considerată ora cu numărul 1.

Exemplu