Advertisement
Guest User

Cavall afamat

a guest
Dec 22nd, 2014
381
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.74 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4.  
  5. using namespace std;
  6. typedef pair<int,bool> cont;
  7. typedef vector< vector<char> > Mat;
  8. typedef vector< vector<cont> > Dist;
  9. typedef pair<int,int> p;
  10.  
  11. void bfs(int i, int j, Dist &dist, queue<p> &q, int f, int c, Mat &mat, int &d) {
  12.     if (i >= 0 and i < f and j >=0 and j < c and dist[i][j].second == false and (mat[i][j] == '.' or mat[i][j] == 'p')) {
  13.         dist[i][j].first = d + 1;
  14.         q.push(p(i,j));
  15.     }
  16. }
  17.  
  18. int main() {
  19.     queue<p> q;
  20.     int f, c;
  21.     while (cin >> f >> c) {
  22.         Mat mat(f, vector<char>(c));
  23.         Dist dist(f, vector<cont>(c));
  24.         for (int i = 0; i < f; ++i) {
  25.             for (int j = 0; j < c; ++j) {
  26.                 cin >> mat[i][j];
  27.             }
  28.         }
  29.         int x, y;
  30.         bool trobat = false;
  31.         int passos = 0;
  32.         int d;
  33.         cin >> x >> y;
  34.         --x;
  35.         --y;
  36.         dist[x][y].first = 0;
  37.         q.push(p(x,y));
  38.         while (not q.empty() and not trobat) {
  39.             pair<int,int> u = q.front();
  40.             q.pop();
  41.             if (mat[u.first][u.second] == 'p') {
  42.                 passos = dist[u.first][u.second].first;
  43.                 trobat = true;
  44.             }
  45.             else if (mat[u.first][u.second] == '.' and dist[u.first][u.second].second == false) {
  46.                 dist[u.first][u.second].second = true;
  47.                 d = dist[u.first][u.second].first;
  48.                 bfs(u.first -2, u.second -1, dist, q, f, c, mat, d);
  49.                 bfs(u.first -2, u.second +1, dist, q, f, c, mat, d);
  50.                 bfs(u.first -1, u.second +2, dist, q, f, c, mat, d);
  51.                 bfs(u.first +1, u.second +2, dist, q, f, c, mat, d);
  52.                 bfs(u.first +2, u.second +1, dist, q, f, c, mat, d);
  53.                 bfs(u.first +2, u.second -1, dist, q, f, c, mat, d);
  54.                 bfs(u.first +1, u.second -2, dist, q, f, c, mat, d);
  55.                 bfs(u.first -1, u.second -2, dist, q, f, c, mat, d);
  56.             }
  57.         }
  58.         if (not trobat) cout << "no" << endl;
  59.         else cout << passos << endl;
  60.     }
  61. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement