Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <queue>
- #include <map>
- using namespace std;
- #define N 110
- int labyrinth[N][N];
- int n, m;
- struct Ver {
- int x, y;
- Ver(int a, int b) {
- x = a;
- y = b;
- }
- };
- queue<Ver>que;
- struct MapCompare
- {
- bool operator() (const Ver& a, const Ver& b) const
- {
- return (a.x > b.x) ? (a.x > b.x) : (a.y > b.y);
- }
- };
- map<Ver, int,MapCompare> top;
- int right(int x,int y) {
- int i = y;
- while (labyrinth[x][i + 1] != 1) {
- i++;
- }
- return i ;
- }
- int left(int x,int y) {
- int i = y;
- while (labyrinth[x][i - 1] != 1) {
- i--;
- }
- return i ;
- }
- int up(int x, int y) {
- int i = x;
- while (labyrinth[i-1][y] != 1) {
- i--;
- }
- return i;
- }
- int down(int x, int y) {
- int i = x;
- while (labyrinth[i+1][y] != 1) {
- i++;
- }
- return i;
- }
- void bfs(int x, int y) {
- map<Ver, int>::iterator it;
- top.insert(pair<Ver, int> (Ver(x,y), 1));
- que.push(Ver(x, y));
- while (que.size() != 0) {
- int a = que.front().x;
- int b = que.front().y;
- cout << a << " " << b << "\n";
- que.pop();
- it = top.find(Ver(a, b));
- cout << it->second << "\n";
- if (labyrinth[a][b] == 2) {
- cout << it->second;
- return;
- }
- int bend = it->second + 1;
- cout << "ben " << bend << "\n";
- int r = right(a, b);
- cout << "r " << r << "\n";
- if (top.count(Ver(a, r)) != 1) {
- que.push(Ver(a, r));
- cout << "PRIV" << "\n";
- top.insert(pair<Ver, int>(Ver(a, r), bend));
- }
- int l = left(a, b);
- cout << "l " << l << "\n";
- if (top.count(Ver(a, l)) != 1) {
- que.push(Ver(a, l));
- cout << "PRIV" << "\n";
- top.insert(pair<Ver, int>(Ver(a, l), bend));
- }
- int u = up(a, b);
- cout << "u " << u << "\n";
- if (top.count(Ver(u, b)) != 1) {
- que.push(Ver(u, b));
- cout << "priv";
- top.insert(pair<Ver, int>(Ver(u, b), bend));
- }
- int d = down(a, b);
- cout << "d " << d << "\n";
- if (top.count(Ver(d, b)) != 1) {
- que.push(Ver(d, b));
- cout << "priv" << "\n";
- top.insert(pair<Ver, int>(Ver(d, b), bend));
- }
- }
- }
- int main() {
- cin >> n >> m;
- for (int i = 1; i <= n ; i++) {
- for (int j = 1; j <= m; j++) {
- cin >> labyrinth[i][j];
- }
- }
- for (int i = 0; i <= m + 1; i++) {
- labyrinth[0][i] = 1;
- labyrinth[n + 1][i] = 1;
- }
- for (int i = 0; i <= n + 1; i++) {
- labyrinth[i][m + 1] = 1;
- labyrinth[i][0] = 1;
- }
- bfs(1, 1);
- return 0;
- }
Add Comment
Please, Sign In to add comment