Advertisement
jonator

Untitled

Dec 18th, 2014
158
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.22 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6.  
  7. typedef vector<vector<char> > Graf;
  8.  
  9. bool pos_ok(int x, int y, int i, int j)
  10. {
  11.   return (i >= 0 and i < x and j >= 0 and j < y);
  12. }
  13.  
  14. void escriure_g(Graf& g, int x, int y) {
  15.   for (int i = 0; i < x; ++i) {
  16.     for (int j = 0; j < y; ++j) {
  17.       cin >> g[i][j];
  18.     }
  19.   }
  20. }
  21.  
  22. void mostrar_g(const Graf& g, int x, int y) {
  23.   for (int i = 0; i < x; ++i) {
  24.     for (int j = 0; j < y; ++j) {
  25.       cout << g[i][j] << " ";
  26.     }
  27.     cout << endl;
  28.   }
  29. }
  30.  
  31. int bfs(Graf& g, int x, int y, int i, int j) {
  32.   int suma = 0;
  33.   int dir[8] = {0, 1, 1, 0, 0, -1, -1, 0};
  34.   queue <pair<int, int> > q;
  35.   q.push(make_pair(i,j));
  36.  
  37.   while(not q.empty()) {
  38.     pair<int, int> p = q.front(); q.pop();
  39.     if(g[p.first][p.second] == 't') ++suma;
  40.     g[p.first][p.second] = 'X';
  41.     for (int i = 0; i < 8; i+=2) {
  42.       int a = p.first+dir[i], b = p.second+dir[i+1];
  43.       if (pos_ok(x,y,a,b) and g[a][b] != 'X') q.push(make_pair(a,b));
  44.     }
  45.   }
  46.   return suma;
  47. }
  48.  
  49. int main()
  50. {
  51.   int x, y;
  52.   cin >> x >> y;
  53.   Graf g (x, vector<char> (y));
  54.   escriure_g(g,x,y);
  55.   int i, j;
  56.   cin >> i >> j;
  57.   --i; --j;
  58.   cout << bfs(g,x,y,i,j) << endl;
  59. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement