# PBinfo #4505 – Mewtwo – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: Darius

## Enunț

Cerința
Ash este un antrenor Pokemon ambițios, setându-și scopul să devină cel mai bun. Din păcate, rivalul său, Gary, a furat startul și are Pokemoni mai puternici decât cei ai lui Ash.

Totuși, Ash nu se va da bătut chiar așa ușor! Are un plan de bătaie: în aventurile sale a găsit o clădire misterioasă care poate fi reprezentată ca o matrice de N x M, fiecare celulă reprezentând conținutul unei camere. În această clădire se află: 


Ash (codificat cu A): Ash se află inițial în această cameră
Mewtwo (codificat cu M): cel mai puternic Pokemon cunoscut de om. Ash are deja un Master Ball, așa că îl va poate prinde pe Mewtwo cu ușurință.
Gary (codificat cu G): a fost provocat de Ash la o bătălie de Pokemoni și îl așteaptă într-o anumită cameră
cameră liberă (codificată cu _): Ash poate accesa această cameră
cameră ocupată (codificată cu #): Ash nu poate accesa această cameră

Planul său constă în a-l prinde pe Mewtwo, după aceea în a-l confrunta pe Gary. Ash se poate deplasa în cele patru direcții cardinale (N, E, S, V). Știind că o deplasare se face într-o secundă, determinați numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.

Date de intrare
Programul citește de la tastatură numerele N și M, reprezentând dimensiunile clădirii misterioase.

Pe următoarele N linii se vor afla șiruri de câte M caractere, reprezentând structura clădirii.

Date de ieșire
Se va afișa numărul minim de secunde în care Ash poate ajunge la Mewtwo, apoi la Gary.

Restricții și precizări

Când zicem cel mai puternic Pokemon, ne referim comparativ cu cei din generația 1.
Se garantează că Ash își va putea executa planul de bătaie
1 ≤ N ≤ 1.000
1 ≤ M ≤ 1.000

Exemplu:
Intrare

8 10
__#_______
_A#_______
__#___M_#_
__#__####_
__##_##___
_____#__G_
__#__#____
__########
Ieșire

21
Explicație
Distanța minimă de la Ash până la Mewtwo este 12, iar distanța minimă de la Mewtwo panâ la Gary este 9. Suma acestor distante este 21.

## Cod sursă C++

```cpp
// Problema Mewtwo - solutie in O(N*M) folosind BFS pe grid - 100 puncte
#include <iostream>
#include <queue>
#include <utility>
// x, y = N, M
// i_ash, j_ash = coordonatele lui Ash
// i_mew2, j_mew2 = coordonatele lui Mewtwo
// i_gary, j_gary = coordonatele lui Gary
// arr = matricea
// dist1[i][j] = distanta de la punctul lui Ash pana la punctul (i, j) + 1
// dist2[i][j] = distanta de la punctul lui Mewtwo pana la punctul (i, j) + 1
int x, y;
int i_ash, j_ash;
int i_mew2, j_mew2;
int i_gary, j_gary;
char arr[1005][1005];
int dist1[1005][1005];
int dist2[1005][1005];
// Vectorii de directie
const int dx[4] = {0,1,0,-1};
const int dy[4] = {1,0,-1,0};
// Verificam daca (i, j) este in matrice
bool in_mat(int i, int j) {
	return !(i<1||i>x||j<1||j>y);
}
// Aceasta functie afla distanta minima de la punctul (is, js) la punctul (ie, je)
// folosind un BFS pe grid (sau Lee)
int bfs(int dist[][1005], int is, int js, int ie, int je) {
	// Bagam punctul de start in coada
	std::queue<std::pair<int,int>> q;
	q.emplace(std::pair<int,int>(is,js));
	// Setam distanta initiala 1, punctele cu distanta 0 fiind nevizitate
	dist[is][js] = 1;
	int i, j;
	while (!q.empty()) {
		// Scoatem punctul din coada
		i = q.front().first;
		j = q.front().second;
		q.pop();
		// Daca am ajuns la destinatie, nu mai are rost sa continuam algoritmul
		if (i==ie&&j==je) break;
		// Incercam sa intram in toate camerele vecine posibile
		for (int k = 0; k < 4; k++) {
			int inou = i+dx[k];
			int jnou = j+dy[k];
			// Verificam daca (inou, jnou) este in matrice, daca nu este vizitat si daca nu este camera blocata
			if (in_mat(inou,jnou)&&!dist[inou][jnou]&&arr[inou][jnou]!='#') {
				dist[inou][jnou] = dist[i][j]+1;
				q.emplace(std::pair<int,int>(inou,jnou));
			}
		}
	}
	// Returnam dist[ie][je]-1 deoarece consideram ca distanta de la punctul de start pana la el insusi este 1, dar defapt este 0
	return dist[ie][je]-1;
}
int main() {
	// Citim matricea
	std::cin >> x >> y;
	for (int i = 1; i <= x; i++) {
		std::cin >> (arr[i]+1);
	}
	// Aflam coordonatele lui Ash, Mewtwo si Gary
	for (int i = 1; i <= x; i++) {
		for (int j = 1; j <= y; j++) {
			if (arr[i][j]=='A') {
				i_ash = i;
				j_ash = j;
			}
			if (arr[i][j]=='M') {
				i_mew2 = i;
				j_mew2 = j;
			}
			if (arr[i][j]=='G') {
				i_gary = i;
				j_gary = j;
			}
		}
	}
	// Afisam numarul minim de secunde cerut
	std::cout << bfs(dist1,i_ash,j_ash,i_mew2,j_mew2) + bfs(dist2,i_mew2,j_mew2,i_gary,j_gary) << "\n";
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/4505)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/4505/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-4505/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)