• Sign Up
• Login
• API
• FAQ
• Tools
• Archive
daily pastebin goal
37%
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.

Top