== include(page="template/taskheader" task_id="joc11") ==
Poveste şi cerinţă...
Doi participanţi, A şi B, joacă un joc pe o tablă de dimensiuni $N x N$. Pătratele tablei sunt fie de culoare albă, fie de culoare neagră. Participanţii vor folosi doar pătratele albe, cele negre fiind excluse din joc. Fiecare jucător are o piesă aşezată pe un pătrat alb numit _locul de start_ al jucătorului. Locurile de start ale celor doi jucători sunt diferite.
O mutare constă în deplasarea piesei unui jucător într-unul din pătratele de culoare albă adiacente pe una din direcţiile: nord, est, sud, vest. Dacă un jucător mută piesa într-o locaţie ocupată deja de oponentul său, atunci câştigă o mutare în plus (în acest fel sare peste oponent). În acest caz, direcţia mutării doi poate fi alta decât cea a mutării întâi.
Participanţii vor muta alternativ, jucătorul A fiind cel care mută primul. Scopul jocului este să se ajungă la locul de start al adversarului. Jucătorul care atinge primul acest scop va câştiga. Chiar dacă un jucător trebuie să efectueze două mutări, sărind peste locul de start al adversarului, acesta va câştiga jocul.
h2. Cerinţă
Se cere să se determine care jucător are strategie sigură de câştig. Un jucător are strategie sigură de câştig dacă va câştiga indiferent de mutările adversarului.
h2. Date de intrare
Fişierul de intrare $joc11.in$ ...
Fişierul de intrare $joc11.in$ conţine pe prima linie un număr $T$, numărul testelor. Descrierile testelor vor fi pe liniile următoare. Pe prima linie a fiecărui test se găseşte un număr întreg $N$, lungimea laturii tablei. Fiecare din următoarele $N$ linii conţin câte $N$ caractere, fără spaţiu alb între acestea. Fiecare caracter este unul din următoarele: $'.'$ (un pătrat alb), $'#'$ (un pătrat negru), $'A'$ (locul de start al jucătorului A), $'B'$ (locul de start al jucătorului B).
h2. Date de ieşire
În fişierul de ieşire $joc11.out$ ...
În fişierul de ieşire $joc11.out$, pentru fiecare test, se va scrie câte o linie cu unul din caracterele $'A'$ sau $'B'$, indicând jucătorul care are strategie sigură de câştig.
h2. Restricţii
h2. Restricţii şi precizări
* $... ≤ ... ≤ ...$
* $1 ≤ T ≤ 6$
* $2 ≤ N ≤ 300$
* Între locurile de start ale celor doi jucători va exista întotdeauna un drum pe pătrate albe.
* Pentru $40%$ din teste $N ≤ 40$.
* Pentru $60%$ din teste $N ≤ 150$.
h2. Exemplu
table(example). |_. joc11.in |_. joc11.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 1
5
.....
A....
..###
.#...
....B
| A
|
h3. Explicaţie
...
Între cei doi jucători există un singur drum de lungime $7$. Dacă jucătorul B nu va alege drumul cel mai scurt atunci el va efectua mai mult de $7$ mutări, deci A va câştiga. Dacă va alege drumul cel mai scurt, jucătorul A va fi cel care va sări peste B câştigând astfel două căsuţe avans datorită cărora va câştiga.
== include(page="template/taskfooter" task_id="joc11") ==
