Guest User

Untitled

a guest
Aug 19th, 2018
70
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> > Graf1;
  8. typedef pair<int,int> iipair;
  9.  
  10. void prova( int i, int j, Graf& mapa, Graf1& dist, queue<iipair>& q, 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(iipair(i,j));
  14. dist[i][j] = d+1;
  15. }
  16. }
  17. }
  18.  
  19.  
  20.  
  21. int main() {
  22. int n, m, contador;
  23. contador = 0;
  24. cin >> n >> m;
  25. Graf g (n,vector<char> (m));
  26. Graf1 dist (n,vector<int> (m, -1));
  27. for (int i = 0; i < n; ++i) {
  28. for (int j = 0; j < m; ++j) cin >> g[i][j];
  29. }
  30. int x, y;
  31. cin >> x >> y;
  32. --x; --y;
  33.  
  34. // bool trobat = false;
  35. queue <iipair> q;
  36. q.push(iipair(x,y));
  37. int d = -1;
  38. dist[x][y] = 0;
  39. while (/*!trobat and*/ q.size()) {
  40. iipair p = q.front();
  41. q.pop();
  42. if (g[p.first][p.second] == 't') {
  43. //trobat = true;
  44. g[p.first][p.second] = '.';
  45. d = dist[p.first][p.second];
  46. contador++;
  47. // cout << "minimum distance: " << d << endl;
  48. }if (g[p.first][p.second] == '.'){
  49. g[p.first][p.second] = 'v'; //visitat
  50. prova(p.first-1,p.second,g,dist,q,dist[p.first][p.second]);
  51. prova(p.first+1,p.second,g,dist,q,dist[p.first][p.second]);
  52. prova(p.first,p.second+1,g,dist,q,dist[p.first][p.second]);
  53. prova(p.first,p.second-1,g,dist,q,dist[p.first][p.second]);
  54. }
  55. }
  56. //if (not trobat) cout << "no treasure can be reached" << endl;
  57. cout << contador << endl;
  58. }
Add Comment
Please, Sign In to add comment