Sokoban

$\text{Claudiu}$ este fascinat de jocuri puzzle de tip $\text{Sokoban}$, în care scopul este împingerea unor cutii la anumite destinații. Simțindu-se dornic de o provocare, el l-a rugat pe prietenul său $\text{ChatGPT}$ să îi creeze un astfel de puzzle. Din păcate, $\text{ChatGPT}$ a greșit implementarea, așa că, pe tot parcursul jocului, player-ul nu se poate îndepărta de marginea cutiei. $\text{Claudiu}$ realizează că puzzle-ul s-ar putea să fie prea greu pentru el, iar cum el trebuie să se pregătească pentru $\text{Olimpiada Județeană de Informatică}$, vă roagă pe voi să găsiți o soluție.

Cerință

Se dă o matrice $N\times M$ reprezentând puzzle-ul creat de $\text{ChatGPT}$. Acesta conține un player, o cutie de dimensiuni $N_c\times M_c$, o poziție unde trebuie să ajungă player-ul, și diverse obstacole. Așadar, fiecare celulă poate fi de următoarele tipuri:

• Un spațiu liber, prin care pot trece atât cutia, cât și player-ul;
• Un obstacol prin care poate trece cutia, dar nu player-ul;
• Un perete prin care nu pot trece nici cutia și nici player-ul;
• Un spațiu liber ocupat de player la început;
• Un spațiu liber ocupat de cutie la început;
• Un spațiu liber ce trebuie ocupat de player la final.

Într-un pas, player-ul se poate mișca în una din cele $4$ direcții cardinale. Dacă cutia ocupă această celulă, ea va fi împinsă în direcția corespunzătoare. Această mutare se poate realiza doar dacă la finalul ei player-ul și cutia ocupă poziții valide. Din cauza greșelii lui $\text{ChatGPT}$, atât la început, cât și la finalul fiecărei mutări, player-ul trebuie să se afle pe marginea cutiei (vezi $\textbf{Restricții și precizări}$ pentru definiții formale).
Să se determine numărul minim de pași necesari pentru ca player-ul să ajungă la destinația sa finală.

Date de intrare

Pe prima linie a fișierului de intrare sokoban.in se găsesc $4$ numere întregi, $N, M, N_c, M_c$, cu semnificația din enunț. Pe următoarele $N$ linii se găsesc câte $M$ caractere, care reprezintă descrierea matricii:

• . - spațiu liber;
• w - obstacol prin care poate trece doar cutia;
• W - perete prin care nu poate trece nimic;
• P - poziția de început a player-ului;
• B - un spațiu ocupat de cutie la început;
• F - destinația finală a player-ului.

Date de ieșire

Pe singura linie a fișierului de ieșire sokoban.out se va afla un singur număr întreg, ce va reprezenta numărul minim de pași pentru ca player-ul să ajungă la destinație.

Restricții și precizări

• $1 \leq N, M \leq 1 \ 000$;
• $1 \leq N_c, M_c \leq 5$;
• Din celula $(i, j)$, player-ul se poate mișca în una din celulele $(i-1, j), (i, j+1), (i+1, j), (i, j-1)$, atât timp cât acestea se află în matrice;
• Celula $(i, j)$ este considerată $\textit{pe marginea cutiei}$ dacă cel puțin una din celulele
  $(i-1, j-1), (i-1, j), (i-1, j+1), (i, j+1), (i+1, j+1), (i+1, j), (i+1, j-1), (i, j-1)$ este ocupată de cutie;
• Se garantează că există exact un caracter P și exact un caracter F în datele de intrare;
• Se garantează că toate caracterele B din datele de intrare formează un dreptunghi $N_c\times M_c$ în matrice;
• Se garantează că player-ul este pe marginea cutiei în poziția inițială dată de datele de intrare;
• Se garantează că player-ul poate ajunge la destinația sa finală urmând regulile descrise ($\text{ChatGPT}$ a avut grijă să creeze un puzzle rezolvabil).

Subtask-uri și punctare

Exemplul 1

sokoban.in

3 3 1 1
WW.
PBF
W..

sokoban.out

4

Explicație

Exemplul 2

sokoban.in

2 5 1 1
.FPB.
WW...

sokoban.out

7

Explicație

Exemplul 3

sokoban.in

3 5 2 2
WWFWW
WBB..
PBB..

sokoban.out

4

Explicație

Exemplul 4

sokoban.in

7 9 5 1
WWWWWWWWw
.Bw.w...w
.B..w.w.w
PBw.w.w.w
.Bw...w.w
.Bw.w.w.F
WWWWWWW..

sokoban.out

20

Explicație