Guest User

Untitled

a guest
Aug 19th, 2018
91
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.68 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. typedef vector < vector <char> > Graf;
  7. typedef vector < vector <int> > Graf2;
  8. typedef pair<int,int> pos;
  9.  
  10. void prova( int i, int j, Graf& mapa, queue<pos>& q, Graf2& dist,int d) {
  11. if (i>=0 and i < mapa.size() and j >= 0 and j < mapa[0].size()) {
  12. if (mapa[i][j] == '.' or mapa[i][j] == 't') {
  13. q.push(pos(i,j));
  14. dist[i][j] = d+1;
  15. }
  16. }
  17. }
  18.  
  19. int main() {
  20. int n, m;
  21. cin >> n >> m;
  22. Graf mapa (n,vector<char> (m));
  23. Graf2 dist (n,vector<int> (m,-1));
  24. for (int i = 0; i < n; ++i) {
  25. for (int j = 0; j < m; ++j) cin >> mapa[i][j];
  26. }
  27. int x, y;
  28. cin >> x >> y;
  29. --x; --y;
  30.  
  31. int numpasos = -1;
  32. bool trobat = false;
  33. queue <pos> q;
  34. q.push(pos(x,y));
  35. dist[x][y] = 0;
  36. while (!trobat and q.size()) {
  37. pos p = q.front();
  38. q.pop();
  39. if (mapa[p.first][p.second] == 't') {
  40. mapa[p.first][p.second] = '.';
  41. if (numpasos < dist[p.first][p.second]) numpasos = dist[p.first][p.second];
  42. }
  43. if (mapa[p.first][p.second] == '.'){
  44. mapa[p.first][p.second] = 'v'; //visitat
  45. prova(p.first-1,p.second,mapa,q,dist, dist[p.first][p.second]);
  46. prova(p.first+1,p.second,mapa,q,dist, dist[p.first][p.second]);
  47. prova(p.first,p.second+1,mapa,q,dist, dist[p.first][p.second]);
  48. prova(p.first,p.second-1,mapa,q,dist, dist[p.first][p.second]);
  49. }
  50. }
  51. if (numpasos != -1) cout << "maximum distance: " << numpasos << endl;
  52. else cout << "no treasure can be reached" << endl;
  53. }
Add Comment
Please, Sign In to add comment