Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- using namespace std;
- struct koord {
- int x, y, dist;
- koord() {
- dist = 0;
- }
- };
- bool BFS(vector<vector<int>> &vec, int &x, int &y, int &endx, int & endy, int &len) {
- queue<koord> q;
- vector<vector<bool>> visited(vec.size(), vector<bool>(vec[0].size(), false));
- koord node;
- if (x == endx && y == endy) return true;
- node.x = x;
- node.y = y;
- q.push(node);
- while (!q.empty()) {
- node = q.front();
- q.pop();
- if (node.x > 0 && vec[node.x - 1][node.y] == 0 && visited[node.x - 1][node.y] != true ) {
- visited[node.x - 1][node.y] = true;
- koord push;
- push.x = node.x - 1;
- push.y = node.y;
- push.dist = node.dist + 1;
- if (push.x == endx && push.y == endy) {
- len = push.dist;
- return true;
- }
- q.push(push);
- }
- if (node.x + 1 < vec.size()) {
- if (vec[node.x + 1][node.y] == 0) {
- if (visited[node.x + 1][node.y] != true) {
- visited[node.x + 1][node.y] = true;
- koord push;
- push.x = node.x + 1;
- push.y = node.y;
- push.dist = node.dist + 1;
- if (push.x == endx && push.y == endy) {
- len = push.dist;
- return true;
- }
- q.push(push);
- }
- }
- }
- if (node.y > 0 && vec[node.x][node.y - 1] == 0 && visited[node.x][node.y - 1] != true) {
- visited[node.x][node.y - 1] = true;
- koord push;
- push.x = node.x;
- push.y = node.y - 1;
- push.dist = node.dist + 1;
- if (push.x == endx && push.y == endy) {
- len = push.dist;
- return true;
- }
- q.push(push);
- }
- if (node.y + 1 < vec[0].size()) {
- if (vec[node.x][node.y + 1] == 0 && visited[node.x][node.y + 1] != true) {
- visited[node.x][node.y + 1] = true;
- koord push;
- push.x = node.x;
- push.y = node.y + 1;
- push.dist = node.dist + 1;
- if (push.x == endx && push.y == endy) {
- len = push.dist;
- return true;
- }
- q.push(push);
- }
- }
- }
- return false;
- }
- int main() {
- int n, m, x, y, endx, endy;
- cin >> n >> m;
- vector<vector<int>> vec(n, vector<int>(m, 1));
- if (m != 0 && n != 0) {
- cin >> x >> y >> endx >> endy;
- for (int i = 0; i < n; i++) {
- for (int j = 0; j < m; j++) {
- cin >> vec[i][j];
- }
- }
- x--; y--; endx--; endy--;
- }
- int len = 0;
- if (m != 0 && n!= 0 && vec[x][y] == 0 && BFS(vec, x, y, endx, endy, len)) {
- cout << len;
- }
- else {
- cout << "NO";
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement