Tesoros2.cpp

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

typedef vector<vector<char> > Mapa;
typedef vector<vector<int> >  Dapa;
typedef pair<int,int> P;

const int X[4] = {1, 0, -1, 0};
const int Y[4] = {0, 1, 0, -1};

int main(){
    int n,m,x,y;
    cin >> n >> m;
    Mapa map(n,vector<char>(m,'.'));
    Dapa dap(n,vector<int> (m,0));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < m; ++j){
            cin >> map[i][j];
        }
    }
    cin >> x >> y;
    --x; --y;
    // Distancia inicial
    dap[x][y] == 0;
    // Posicion inicial
    P inicial;
    inicial.first = x;
    inicial.second = y;
    queue<P> Q;
    Q.push(inicial);
    int res = 0;
    bool trobat = false;
    // mientras no hayamos encontrado tesoros y la cola no esté vacía...
    while(not trobat and not Q.empty()){
        P act = Q.front();
        Q.pop();
        if(map[act.first][act.second] == 't'){
            trobat = true;
            res = dap[act.first][act.second];
        }else if(map[act.first][act.second] == '.'){
            map[act.first][act.second] = 'v';
            // Cuatro direcciones;
            for(int i = 0; i < 4; ++i){
                int xx = act.first + X[i];
                int yy = act.second + Y[i];
                // si la posicion que miramos es válida...
                if(xx >= 0 and xx < map.size() and yy >= 0 and yy < map[0].size()){
                    if(map[xx][yy] == '.' or map[xx][yy] == 't'){
                        Q.push(P(xx,yy));
                        dap[xx][yy] = dap[act.first][act.second] + 1;
                    }
                }
            }
        }
    }
    if(trobat) cout << "distancia minima: " << res << endl;
    else cout << "no es pot arribar a cap tresor" << endl;
}