Advertisement
Guest User

fasdfasdfdasf

a guest
Mar 5th, 2015
175
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.09 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. struct koord {
  7.     int x, y, dist;
  8.     koord() {
  9.         dist = 0;
  10.     }
  11. };
  12.  
  13. bool BFS(vector<vector<int>> &vec, int &x, int &y, int &endx, int & endy, int &len) {
  14.     queue<koord> q;
  15.     vector<vector<bool>> visited(vec.size(), vector<bool>(vec[0].size(), false));
  16.     koord node;
  17.     if (x == endx && y == endy) return true;
  18.     node.x = x;
  19.     node.y = y;
  20.     q.push(node);
  21.     while (!q.empty()) {
  22.         node = q.front();
  23.         q.pop();
  24.         if (node.x > 0 && vec[node.x - 1][node.y] == 0 && visited[node.x - 1][node.y] != true ) {
  25.             visited[node.x - 1][node.y] = true;
  26.             koord push;
  27.             push.x = node.x - 1;
  28.             push.y = node.y;
  29.             push.dist = node.dist + 1;
  30.             if (push.x == endx && push.y == endy) {
  31.                 len = push.dist;
  32.                 return true;
  33.             }
  34.             q.push(push);
  35.         }
  36.         if (node.x + 1 < vec.size()) {
  37.             if (vec[node.x + 1][node.y] == 0) {
  38.                 if (visited[node.x + 1][node.y] != true) {
  39.                     visited[node.x + 1][node.y] = true;
  40.                     koord push;
  41.                     push.x = node.x + 1;
  42.                     push.y = node.y;
  43.                     push.dist = node.dist + 1;
  44.                     if (push.x == endx && push.y == endy) {
  45.                         len = push.dist;
  46.                         return true;
  47.                     }
  48.                     q.push(push);
  49.                 }
  50.             }
  51.         }
  52.         if (node.y > 0 && vec[node.x][node.y - 1] == 0 && visited[node.x][node.y - 1] != true) {
  53.             visited[node.x][node.y - 1] = true;
  54.             koord push;
  55.             push.x = node.x;
  56.             push.y = node.y - 1;
  57.             push.dist = node.dist + 1;
  58.             if (push.x == endx && push.y == endy) {
  59.                 len = push.dist;
  60.                 return true;
  61.             }
  62.             q.push(push);
  63.         }
  64.         if (node.y + 1 < vec[0].size()) {
  65.             if (vec[node.x][node.y + 1] == 0 && visited[node.x][node.y + 1] != true) {
  66.                 visited[node.x][node.y + 1] = true;
  67.                 koord push;
  68.                 push.x = node.x;
  69.                 push.y = node.y + 1;
  70.                 push.dist = node.dist + 1;
  71.                 if (push.x == endx && push.y == endy) {
  72.                     len = push.dist;
  73.                     return true;
  74.                 }
  75.                 q.push(push);
  76.             }
  77.         }
  78.     }
  79.     return false;
  80. }
  81.  
  82.  
  83.  
  84. int main() {
  85.     int n, m, x, y, endx, endy;
  86.     cin >> n >> m;
  87.     vector<vector<int>> vec(n, vector<int>(m, 1));
  88.     if (m != 0 && n != 0) {
  89.         cin >> x >> y >> endx >> endy;
  90.         for (int i = 0; i < n; i++) {
  91.             for (int j = 0; j < m; j++) {
  92.                 cin >> vec[i][j];
  93.             }
  94.         }
  95.         x--; y--; endx--; endy--;
  96.     }
  97.     int len = 0;
  98.     if (m != 0 && n!= 0 && vec[x][y] == 0 && BFS(vec, x, y, endx, endy, len)) {
  99.         cout << len;
  100.     }
  101.     else {
  102.         cout << "NO";
  103.     }
  104. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement