Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- typedef pair<int,bool> cont;
- typedef vector< vector<char> > Mat;
- typedef vector< vector<cont> > Dist;
- typedef pair<int,int> p;
- void bfs(int i, int j, Dist &dist, queue<p> &q, int f, int c, Mat &mat, int &d) {
- 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')) {
- dist[i][j].first = d + 1;
- q.push(p(i,j));
- }
- }
- int main() {
- queue<p> q;
- int f, c;
- while (cin >> f >> c) {
- Mat mat(f, vector<char>(c));
- Dist dist(f, vector<cont>(c));
- for (int i = 0; i < f; ++i) {
- for (int j = 0; j < c; ++j) {
- cin >> mat[i][j];
- }
- }
- int x, y;
- bool trobat = false;
- int passos = 0;
- int d;
- cin >> x >> y;
- --x;
- --y;
- dist[x][y].first = 0;
- q.push(p(x,y));
- while (not q.empty() and not trobat) {
- pair<int,int> u = q.front();
- q.pop();
- if (mat[u.first][u.second] == 'p') {
- passos = dist[u.first][u.second].first;
- trobat = true;
- }
- else if (mat[u.first][u.second] == '.' and dist[u.first][u.second].second == false) {
- dist[u.first][u.second].second = true;
- d = dist[u.first][u.second].first;
- bfs(u.first -2, u.second -1, dist, q, f, c, mat, d);
- bfs(u.first -2, u.second +1, dist, q, f, c, mat, d);
- bfs(u.first -1, u.second +2, dist, q, f, c, mat, d);
- bfs(u.first +1, u.second +2, dist, q, f, c, mat, d);
- bfs(u.first +2, u.second +1, dist, q, f, c, mat, d);
- bfs(u.first +2, u.second -1, dist, q, f, c, mat, d);
- bfs(u.first +1, u.second -2, dist, q, f, c, mat, d);
- bfs(u.first -1, u.second -2, dist, q, f, c, mat, d);
- }
- }
- if (not trobat) cout << "no" << endl;
- else cout << passos << endl;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement