Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- using namespace std;
- int A[100][100], startX, startY, endX, endY;
- int used[100][100];
- struct pos
- {
- int x;
- int y;
- int dist;
- };
- bool valid(int i, int j, int n)
- {
- if (i < 0 || i >= n || j < 0 || j >= n)
- return 0;
- if (A[i][j] == 1)
- return 0;
- return 1;
- }
- int bfs(int n)
- {
- queue<pos> q;
- pos startPos;
- startPos.x = startX;
- startPos.y = startY;
- startPos.dist = 0;
- q.push(startPos);
- while (!q.empty())
- {
- pos currPos = q.front();
- if (currPos.x == endX && currPos.y == endY)
- return currPos.dist;
- if (!used[currPos.x][currPos.y])
- {
- if (valid(currPos.x + 1, currPos.y, n))
- {
- pos newPos;
- newPos.x = currPos.x + 1;
- newPos.y = currPos.y;
- newPos.dist = currPos.dist + 1;
- q.push(newPos);
- }
- if (valid(currPos.x - 1, currPos.y, n))
- {
- pos newPos;
- newPos.x = currPos.x - 1;
- newPos.y = currPos.y;
- newPos.dist = currPos.dist + 1;
- q.push(newPos);
- }
- if (valid(currPos.x, currPos.y + 1, n))
- {
- pos newPos;
- newPos.x = currPos.x;
- newPos.y = currPos.y + 1;
- newPos.dist = currPos.dist + 1;
- q.push(newPos);
- }
- if (valid(currPos.x, currPos.y - 1, n))
- {
- pos newPos;
- newPos.x = currPos.x;
- newPos.y = currPos.y - 1;
- newPos.dist = currPos.dist + 1;
- used[currPos.x][currPos.y - 1] = 1;
- q.push(newPos);
- }
- used[currPos.x][currPos.y] = 1;
- }
- q.pop();
- }
- }
- int main()
- {
- int n;
- cin >> n;
- for (int i = 0; i < n; ++i)
- for (int j = 0; j < n; ++j)
- cin >> A[i][j];
- cin >> startX >> startY >> endX >> endY;
- cout << bfs(n) << endl;
- return 0;
- }
- /*
- 3
- 0 0 0
- 0 0 0
- 0 0 0
- 0 0 2 2
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement