InfoAs Atlas

<- Go back View preview

Problema JocDeSah

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

RAU-Gigel se gândește la un joc cu piesele de șah. El desenează o tablă de șah sub forma unei matrici pătratice de latură `N` și așează în fiecare dintre cele `N × N` celule câte o piesă de șah. Se consideră că dispune de `N × N` exemplare din fiecare piesă posibilă (regi, regine, ture, nebuni, cai, pioni), iar culoarea nu este relevantă. RAU-Gigel se întreabă care este numărul minim de căsuțe (celule) prin care trebuie să treacă un rege oarecare ca să ajungă la o regină oarecare. Regele se poate deplasa câte o celulă în patru direcții posibile: N, E, S, V.  
  
Dar asta nu e tot. La începutul jocului, toți regii au `16` vieți. Atunci când RAU-Gigel mută un rege (oarecare) peste primul pion, acesta pierde o viață. Vestea bună este că, după aceea, regele respectiv poate lua oricâți pioni fără ca numărul său de vieți să fie afectat. Când ia un cal, regele pierde două vieți, dar după aceea poate lua, fără pierderi, oricâți cai. La fel se întâmplă și în cazul nebunilor, primul nebun îl costa patru vieți și, respectiv al turelor, care îl costă opt vieți.  
  
RAU-Gigel dorește să afle ce rege să aleagă și pe ce traseu trebuie să meargă acesta către o regină oarecare, astfel încât la sfârșitul jocului să îi rămână cât mai multe vieți, iar traseul să fie cât mai scurt.

## Cerință

Se cer:

1. Care este numărul maxim de vieți cu care rămâne regele ales?
  2. Prin câte căsuțe trece traseul de lungime minimă? Ce rege mută și pe ce traseu? Dacă există mai multe drumuri de lungime minimă, atunci se va determina drumul mai mic alfanumeric (o celulă este mai mică alfanumeric decât altă celulă dacă se află pe un rând cu indice mai mic sau se află pe același rând cu cea de-a doua, dar pe o coloană cu indice mai mic).

## Date de intrare

Fișierul de intrare `jocdesah.in` conține pe prima linie un număr natural `A`. Pentru toate testele de intrare, numărul `A` poate avea doar valoarea `1` sau valoarea `2`. Pe al doilea rând se găsește numărul natural `N`, cu semnificația din enunț. Pe următoarele `N` linii se află câte `N` litere mari cu următoarea semnificație: `P` – pion, `C` – cal, `N` – nebun, `T` – tură, `Q` – regină și `K` – rege. Caracterele de pe fiecare rând nu au spații între ele.
## Date de ieșire

Dacă valoarea lui `A` este `1`, se va rezolva numai punctul a) din cerință. În acest caz, fișierul de ieșire `jocdesah.out` va conține un singur număr natural ce reprezintă numărul de vieți care îi rămân la sfârșitul jocului regelui ales de RAU-Gigel.  
  
Dacă valoarea lui `A` este `2`, se va rezolva numai punctul b) din cerință. În acest caz, fişierul de ieşire `jocdesah.out` va conține pe prima linie numărul natural `K` ce reprezintă numărul de căsuțe prin care trece regele ales (se numără atât căsuța din care pleacă, cât și cea în care ajunge), apoi pe următoarele `K` rânduri sunt perechi de forma `i j` (separate cu un singur spațiu) unde `i` și `j` reprezintă linia, respectiv coloana celulelor prin care trece regele (în ordinea de deplasare). Indexarea rândurilor și coloanelor se face de la `1` la `N`.
## Restricții și precizări

* `2 ≤ N ≤ 100`
  * În fiecare test există cel puțin o literă `K` și cel puțin o literă `Q`
  * Pentru rezolvarea corectă a primei cerințe se acordă 45 de puncte

Examples

[{"input": "2\n6\nPCQPNP\nPCCCCP\nQNPKPK\nPCKPPP\nNKPPPP\nNNPPQP", "output": "5\n3 4\n3 5\n4 5\n5 5\n6 5", "explanation": "Explica\u021bia primului exemplu \nRAU-Gigel va alege s\u0103 mute regele de pe pozi\u021bia <code>3 4</code>. Drumul va trece prin <code>5</code> celule (va num\u0103ra inclusiv celulele de plecare \u0219i sosire), iar acestea sunt: <code>3 4, 3 5, 4 5, 5 5, 6 5</code>. \u00cen drumul s\u0103u a luat doar pioni, deci a pierdut o singur\u0103 via\u021b\u0103, i-au r\u0103mas <code>15</code>: \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>* * * K P *</code> \n<code>* * * * P *</code> \n<code>* * * * P *</code> \n<code>* * * * Q *</code> Se observ\u0103 c\u0103 mai exist\u0103 un drum de lungime <code>5</code> care \u00eel cost\u0103 tot o singur\u0103 via\u021b\u0103: \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>* * * K * *</code> \n<code>* * * P P *</code> \n<code>* * * * P *</code> \n<code>* * * * Q *</code> Drumul este <code>3 4, 4 4, 4 5, 5 5, 6 5</code>, dar el este mai mic alfanumeric dec\u00e2t <code>3 4, 3 5, 4 5, 5 5, 6 5</code> (perechea <code>3 5</code> e mai mic\u0103 alfanumeric dec\u00e2t perechea <code>4 4</code>). De asemenea, un alt drum este: 3 4, 3 3, 3 2, 3 1: \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>Q N P K * *</code> \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>* * * * * *</code> \nAcesta chiar mai scurt (trece prin numai <code>4</code> c\u0103su\u021be), totu\u0219i pe acest drum regele ar ataca un pion \u0219i un nebun, care l-ar costa <code>1 + 4 = 5</code> vie\u021bi \u0219i ar r\u0103m\u00e2ne cu numai <code>11</code>, de aceea nu \u00eel va alege."}, {"input": "1\n6\nPCQPNP\nPCCCCP\nQNPKPK\nPCKPPP\nNKPPPP\nNNPPQP", "output": "15", "explanation": "Explica\u021bia primului exemplu \nRAU-Gigel va alege s\u0103 mute regele de pe pozi\u021bia <code>3 4</code>. Drumul va trece prin <code>5</code> celule (va num\u0103ra inclusiv celulele de plecare \u0219i sosire), iar acestea sunt: <code>3 4, 3 5, 4 5, 5 5, 6 5</code>. \u00cen drumul s\u0103u a luat doar pioni, deci a pierdut o singur\u0103 via\u021b\u0103, i-au r\u0103mas <code>15</code>: \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>* * * K P *</code> \n<code>* * * * P *</code> \n<code>* * * * P *</code> \n<code>* * * * Q *</code> Se observ\u0103 c\u0103 mai exist\u0103 un drum de lungime <code>5</code> care \u00eel cost\u0103 tot o singur\u0103 via\u021b\u0103: \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>* * * K * *</code> \n<code>* * * P P *</code> \n<code>* * * * P *</code> \n<code>* * * * Q *</code> Drumul este <code>3 4, 4 4, 4 5, 5 5, 6 5</code>, dar el este mai mic alfanumeric dec\u00e2t <code>3 4, 3 5, 4 5, 5 5, 6 5</code> (perechea <code>3 5</code> e mai mic\u0103 alfanumeric dec\u00e2t perechea <code>4 4</code>). De asemenea, un alt drum este: 3 4, 3 3, 3 2, 3 1: \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>Q N P K * *</code> \n<code>* * * * * *</code> \n<code>* * * * * *</code> \n<code>* * * * * *</code> \nAcesta chiar mai scurt (trece prin numai <code>4</code> c\u0103su\u021be), totu\u0219i pe acest drum regele ar ataca un pion \u0219i un nebun, care l-ar costa <code>1 + 4 = 5</code> vie\u021bi \u0219i ar r\u0103m\u00e2ne cu numai <code>11</code>, de aceea nu \u00eel va alege."}]

Default code

Summary

Editorial

_Problemă și editorial propuse de Daniela Alexandra Crisan._

Pentru aflarea lungimii minime a drumului dintre un rege și o regină se utilizează BFS sau algoritmul lui Lee. Acesta se rulează de mai multe ori, pentru diferite combinații de piese care pot fi folosite la o parcurgere, plecând de la combinația cu pierdere minimă. De exemplu, se începe cu damage `0` vieți (posibilă atunci un rege și o regină sunt alăturate), apoi se încearcă parcurgerea numai cu pioni (pierdere o viață), apoi numai cu cai (pierdere `2` vieți), urmează parcurgere cu pioni și cai (pierdere `1 + 2 = 3` vieți). Ordinea încercărilor este: `0` – nicio piesă, `1` – pioni, `2` – cai, `3` – pioni și cai, `4` – numai nebuni, `5` – pioni și nebuni, `6` – cai și nebuni, …., `15` – toate piesele: pioni (`1`), cai (`2`), nebuni (`4`) și ture (`8`). Pentru a genera aceste combinații, se va lucra pe numere de la `0` la `15`, la nivel de biți (măști de biți).

Ne oprim din căutare la prima parcurgere (cu cost minim) care ne arată că există un drum între un rege și o regină. Inițial se pun în coadă toți regii în ordinea citirii / parcurgerii matricei de intrare (de sus în jos și de la stânga la dreapta). De asemenea, ordinea de adăugare a vecinilor în coadă se face ținând cont de ordinea lexicografică cerută în enunț: N, V, E, S. Prima regină întâlnită ne indică drumul de cost minim, de lungime minimă și minim alfanumeric. Traseul urmat se poate obține folosind o matrice auxiliară sau refăcând drumul.

Solution

```
#include <bits/stdc++.h>
using namespace std;

ifstream in("jocdesah.in");
ofstream out("jocdesah.out");

#define INF 1e9
#define NR_VIETI 16
#define MAX 101

int N, Drum[MAX][MAX], Dx[] = { -1, 0, 0, 1 }, Dy[] = { 0, -1, 1, 0 } /*N, V, E, S*/, Optiune;
char A[MAX][MAX];
int V = INF, Cost = INF;

struct Punct {
    int x, y;
}Pt;

struct Nod {
    Punct pt;
    int drum;
}nod_c;

vector <Punct>Regine;
vector <Punct>Regi;
vector<int>Sol;
queue <Nod> Coada;
map<char, int> Val = { {'P', 0}, {'C', 1}, {'N', 2}, {'T', 3} };

void citire() {
 in >> Optiune>> N;
 char c[MAX];
 for (int i = 1; i <= N; i++) {
 in>>c;
 for (int j = 1; j <= N; j++)
 {
 A[i][j] = c[j - 1];
 if (A[i][j] == 'Q')
 Regine.push_back({ i,j });
 if (A[i][j] == 'K')
 Regi.push_back({ i,j });
 }
 }
}

bool este_rege(Punct pt)
{
    for (Punct p : Regi)
        if (p.x == pt.x && p.y==pt.y)
            return true;
    return false;
}

Punct cauta_rege_drum_min()
{
 int min = INF, imin = -1;
 for (int i = 0; i < Regi.size(); i++)
 if (min > Drum[Regi[i].x][Regi[i].y])
 min = Drum[Regi[i].x][Regi[i].y], imin = i;
 if(imin!=-1)
 return { Regi[imin].x, Regi[imin].y };
 return { 0, 0 };
}

bool este_valid(int x, int y) {
 return x >= 1 && y >= 1 && x <= N && y <= N;
}

bool este_setat(char a, int b) {
 return a=='K' || (1 << Val[a]) & b;
}

void rezolvare(int v) {
 while (!Coada.empty()) {
 nod_c = Coada.front();
 Coada.pop();
 if (Drum[nod_c.pt.x][nod_c.pt.y] > nod_c.drum) {
 Drum[nod_c.pt.x][nod_c.pt.y] = nod_c.drum;
 
 for (int k = 0; k < 4; k++) {
 int x = nod_c.pt.x + Dx[k], y = nod_c.pt.y + Dy[k];
 int drum = nod_c.drum + 1;
 if (este_valid(x, y) && este_setat(A[x][y], v))
 Coada.push({ x, y, drum });
 }
 }
 }
}

void refa_drum(Punct pt, int cost)
{
 Sol.clear();
 
 while (cost-- > 1)
 {
 for (int i = 0; i < 4; i++)
 {
 int x1 = pt.x + Dx[i], y1 = pt.y + Dy[i];
 if (este_valid(x1, y1) && Drum[x1][y1] == cost)
 {
 pt.x = x1; pt.y = y1;
 Sol.push_back(i);
 break;
 }
 }
 }
}

void initializare()
{
 for (int i = 1; i <= N; i++)
 for (int j = 1; j <= N; j++)
 Drum[i][j] = INF;
 for (Punct pt : Regine)
 Coada.push({ pt, 1 });
}

void afisare()
{
 if (Optiune == 1)
 out << NR_VIETI - V;
 else
 {
 out << Cost << "\n";
 out << Pt.x << " " << Pt.y << "\n";
 for (int i : Sol)
 out << (Pt.x += Dx[i]) << " " << (Pt.y += Dy[i]) << "\n";
 }
}

int main()
{
 citire();
 
 for (int v = 0; v <= 15; v++)
 {
 initializare();

rezolvare(v);
        Pt = cauta_rege_drum_min();

if (Pt.x * Pt.y != 0)
        {
            V = v; Cost = Drum[Pt.x][Pt.y];
         
            if (Optiune == 2)
                refa_drum(Pt, Cost);
            break;
        }
    }

afisare();
    
    return 0;
}
```

Contributor ID

Author

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	3 KB	View
0-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
0-jocdesah.ok	/ 100	10 January 2025 21:26	2 B	View
1-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
1-jocdesah.ok	/ 100	10 January 2025 21:26	2 B	View
2-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
2-jocdesah.ok	/ 100	10 January 2025 21:26	17 B	View
3-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
3-jocdesah.ok	/ 100	10 January 2025 21:26	2 B	View
4-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
4-jocdesah.ok	/ 100	10 January 2025 21:26	17 B	View
5-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
5-jocdesah.ok	/ 100	10 January 2025 21:26	2 B	View
6-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
6-jocdesah.ok	/ 100	10 January 2025 21:26	13 B	View
7-jocdesah.in	/ 100	10 January 2025 21:26	114 B	View
7-jocdesah.ok	/ 100	10 January 2025 21:26	2 B	View
8-jocdesah.in	/ 100	10 January 2025 21:26	114 B	View
8-jocdesah.ok	/ 100	10 January 2025 21:26	33 B	View
9-jocdesah.in	/ 100	10 January 2025 21:26	114 B	View
9-jocdesah.ok	/ 100	10 January 2025 21:26	51 B	View
10-jocdesah.in	/ 100	10 January 2025 21:26	2 KB	View
10-jocdesah.ok	/ 100	10 January 2025 21:26	157 B	View
11-jocdesah.in	/ 100	10 January 2025 21:26	9 KB	View
11-jocdesah.ok	/ 100	10 January 2025 21:26	1 B	View
12-jocdesah.in	/ 100	10 January 2025 21:26	9 KB	View
12-jocdesah.ok	/ 100	10 January 2025 21:26	583 B	View
13-jocdesah.in	/ 100	10 January 2025 21:26	9 KB	View
13-jocdesah.ok	/ 100	10 January 2025 21:26	1 B	View
14-jocdesah.in	/ 100	10 January 2025 21:26	9 KB	View
14-jocdesah.ok	/ 100	10 January 2025 21:26	1 KB	View
15-jocdesah.in	/ 100	10 January 2025 21:26	33 B	View
15-jocdesah.ok	/ 100	10 January 2025 21:26	1 B	View
16-jocdesah.in	/ 100	10 January 2025 21:26	33 B	View
16-jocdesah.ok	/ 100	10 January 2025 21:26	25 B	View
17-jocdesah.in	/ 100	10 January 2025 21:26	114 B	View
17-jocdesah.ok	/ 100	10 January 2025 21:26	2 B	View
18-jocdesah.in	/ 100	10 January 2025 21:26	114 B	View
18-jocdesah.ok	/ 100	10 January 2025 21:26	21 B	View
19-jocdesah.in	/ 100	10 January 2025 21:26	45 B	View
19-jocdesah.ok	/ 100	10 January 2025 21:26	9 B	View
In total: 42 files 48 KB

Problema JocDeSah

Identification properties

Content properties

Technical properties

Delete all files