daily pastebin goal
47%
SHARE
TWEET

Untitled

a guest Mar 19th, 2018 256 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top