Advertisement
Guest User

Untitled

a guest
Aug 22nd, 2020
380
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define INF 999999999
  3. #define N 2000
  4. #define mkp(a,b) make_pair(a,b)
  5. #define sz(c) (int)(c).size()
  6. using namespace std;
  7. int h , w , ch , cw , dh , dw , dp[N][N] , ans = INF;
  8. char a[N][N];
  9. int movex[] = {1 , 0 , -1 , 0};
  10. int movey[] = {0 , 1 , 0 , -1};
  11. queue < pair<int,int> > q;
  12. bool check(int x , int y){
  13.     if(x < 0 || y < 0) return 0;
  14.     if(x >= h || y >= w) return 0;
  15.     return 1;
  16. }
  17. int main(){
  18.     cin >> h >> w;
  19.     cin >> ch >> cw;
  20.     cin >> dh >> dw;
  21.     dh--; dw--;
  22.     ch--; cw--;
  23.     for(int i = 0 ; i < h ; i++){
  24.         for(int j = 0 ;j < w ; j++) cin >> a[i][j];
  25.     }
  26.     for(int i = 0 ; i < h ; i++){
  27.         for(int j = 0 ; j < w ; j++){
  28.             dp[i][j] =INF;
  29.         }
  30.     }
  31.     dp[ch][cw] = 0;
  32.     q.push(mkp(ch,cw));
  33.     while(sz(q) > 0){
  34.         pair<int,int> p = q.front();
  35.         int x = p.first , y = p.second;
  36.         q.pop();
  37.         for(int i = x-2 ; i <= x + 2 ; i++){
  38.                 for(int j = y-2 ; j <= y+2 ; j++){
  39.                     if(!check(i,j)) continue;
  40.                     int d = abs(i-x) + abs(j-y) <= 1 ? 0 : 1;
  41.                     if(a[i][j]=='.' && dp[i][j]>dp[x][y]+d) {
  42.                         dp[i][j] = dp[x][y] + d;
  43.                         q.push(mkp(i,j));
  44.                     }
  45.                 }
  46.         }        
  47.     }
  48.     if(dp[dh][dw] == INF) cout <<"-1";
  49.     else cout << dp[dh][dw] << '\n';
  50.  
  51. }
  52.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement