Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef vector < vector <char> > Graf;
- typedef vector < vector <int> > Graf2;
- typedef pair<int,int> pos;
- void prova( int i, int j, Graf& mapa, queue<pos>& q, Graf2& dist,int d) {
- if (i>=0 and i < mapa.size() and j >= 0 and j < mapa[0].size()) {
- if (mapa[i][j] == '.' or mapa[i][j] == 't') {
- q.push(pos(i,j));
- dist[i][j] = d+1;
- }
- }
- }
- int main() {
- int n, m;
- cin >> n >> m;
- Graf mapa (n,vector<char> (m));
- Graf2 dist (n,vector<int> (m,-1));
- for (int i = 0; i < n; ++i) {
- for (int j = 0; j < m; ++j) cin >> mapa[i][j];
- }
- int x, y;
- cin >> x >> y;
- --x; --y;
- int numpasos = -1;
- bool trobat = false;
- queue <pos> q;
- q.push(pos(x,y));
- dist[x][y] = 0;
- while (!trobat and q.size()) {
- pos p = q.front();
- q.pop();
- if (mapa[p.first][p.second] == 't') {
- mapa[p.first][p.second] = '.';
- if (numpasos < dist[p.first][p.second]) numpasos = dist[p.first][p.second];
- }
- if (mapa[p.first][p.second] == '.'){
- mapa[p.first][p.second] = 'v'; //visitat
- prova(p.first-1,p.second,mapa,q,dist, dist[p.first][p.second]);
- prova(p.first+1,p.second,mapa,q,dist, dist[p.first][p.second]);
- prova(p.first,p.second+1,mapa,q,dist, dist[p.first][p.second]);
- prova(p.first,p.second-1,mapa,q,dist, dist[p.first][p.second]);
- }
- }
- if (numpasos != -1) cout << "maximum distance: " << numpasos << endl;
- else cout << "no treasure can be reached" << endl;
- }
Add Comment
Please, Sign In to add comment