Guest User

Untitled

a guest
Mar 19th, 2018
306
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.98 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int INF = 1000000000;
  6. char c[50][50];
  7. int H, W, sy, sx, gy, gx, d[50][50], dy[4] = {1, 0, -1, 0}, dx[4] = {0, 1, 0, -1};
  8.  
  9. int bfs() {
  10. for (int i = 0; i < H; i++) {
  11. for (int j = 0; j < W; j++)
  12. d[i][j] = INF;
  13. }
  14. queue<pair<int, int> > q;
  15. q.push(make_pair(sy, sx));
  16. d[sy][sx] = 0;
  17. while (q.size()) {
  18. pair<int, int> p = q.front();
  19. q.pop();
  20. for (int i = 0; i < 4; i++) {
  21. int ny = p.first + dy[i], nx = p.second + dx[i];
  22. if (0 <= ny && ny < H && 0 <= nx && nx < W && c[ny][nx] != '#' && d[ny][nx] == INF) {
  23. q.push(make_pair(ny, nx));
  24. d[ny][nx] = d[p.first][p.second] + 1;
  25. }
  26. }
  27. }
  28. return d[gy][gx];
  29. }
  30.  
  31. void solve() {
  32. int x = bfs();
  33. printf("%d\n", x);
  34. return;
  35. }
  36.  
  37. int main() {
  38. cin >> H >> W >> sy >> sx >> gy >> gx;
  39. sy -= 1; sx -= 1; gy -= 1; gx -= 1;
  40. for (int i = 0; i < H; i++) {
  41. for (int j = 0; j < W; j++) {
  42. cin >> c[i][j];
  43. }
  44. }
  45. solve();
  46. return 0;
  47. }
Add Comment
Please, Sign In to add comment