Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- int n, m;
- struct data
- {
- int why, ex;
- };
- int bfs(int levels[1010][1010], bool vis[1010][1010], char arr[1010][1010], int siz, int x, int y, int tx, int ty)
- {
- int pntr = -1;
- struct data d[siz];
- pntr++;
- d[pntr].why = y;
- d[pntr].ex = x;
- vis[y][x] = true;
- levels[y][x] = 0;
- while(pntr >= 0)
- {
- struct data temp = d[pntr];
- pntr--;
- int sy = temp.why;
- int sx = temp.ex;
- if(isalpha(arr[sy + 1][sx])) cout << "sakib";
- if(sy + 1 && sx && sy + 1 <= n && sx <= m && isalnum(arr[sy + 1][sx]) && !vis[sy + 1][sx] && arr[sy + 1][sx] != '*')
- {
- vis[sy + 1][sx] = true;
- pntr++;
- d[pntr].why = sy + 1;
- d[pntr].ex = sx;
- levels[sy + 1][sx] = levels[sy][sx] + 1;
- if(sy + 1 == ty && sx == tx) return levels[sy + 1][sx];
- }
- if(sy - 1 && sx && sy - 1 <= n && sx <= m && isalnum(arr[sy - 1][sx]) && !vis[sy - 1][sx] && arr[sy - 1][sx] != '*')
- {
- vis[sy - 1][sx] = true;
- pntr++;
- d[pntr].why = sy - 1;
- d[pntr].ex = sx;
- levels[sy - 1][sx] = levels[sy][sx] + 1;
- if(sy - 1 == ty && sx == tx) return levels[sy - 1][sx];
- }
- if(sy && sx + 1 && sy <= n && sx + 1 <= m && isalnum(arr[sy][sx + 1]) && !vis[sy][sx + 1] && arr[sy][sx + 1] != '*')
- {
- vis[sy][sx + 1] = true;
- pntr++;
- d[pntr].why = sy;
- d[pntr].ex = sx + 1;
- levels[sy][sx + 1] = levels[sy][sx] + 1;
- if(sy == ty && sx + 1 == tx) return levels[sy][sx + 1];
- }
- if(sy && sx - 1 && sy <= n && sx - 1 <= m && isalnum(arr[sy][sx - 1]) && !vis[sy][sx - 1] && arr[sy][sx - 1] != '*')
- {
- vis[sy][sx - 1] = true;
- pntr++;
- d[pntr].why = sy;
- d[pntr].ex = sx - 1;
- levels[sy][sx - 1] = levels[sy][sx] + 1;
- if(sy == ty && sx - 1 == tx) return levels[sy][sx - 1];
- }
- }
- return -1;
- }
- int main()
- {
- char arr[1010][1010];
- int x, y, q;
- cin >> n >> m;
- for(int i = 1; i <= n; i++)
- {
- for(int j = 1; j <= m; j++)
- {
- cin >> arr[i][j];
- }
- }
- cin >> x >> y;
- cin >> q;
- while(q--)
- {
- bool vis[1010][1010] = {false};
- int levels[1010][1010] = {0};
- int tx, ty;
- cin >> tx >> ty;
- if(arr[ty][tx] == '*')
- {
- cout << -1 << " " << -1 << endl;
- continue;
- }
- int distance = bfs(levels, vis, arr, n * m, x, y, tx, ty);
- if(distance == -1) cout << -1 << " " << -1 << endl;
- else cout << distance << "something" << endl; //edit here
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement