| Fişierul intrare/ieşire: | joc11.in, joc11.out | Sursă | Summer Challenge 2009, Runda 1 |
| Autor | Din Folclor | Adăugată de |  Marius Stroe •Marius |
| Timp execuţie pe test | 0.475 sec | Limită de memorie | 36864 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Joc11
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.
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.
Date de intrare
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).
Date de ieşire
Î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.
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.
Exemplu
| joc11.in | joc11.out |
|---|---|
| 1 5 ..... A.... ..### .#... ....B | A |
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.
