Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define INF 999999999
- #define N 2000
- #define mkp(a,b) make_pair(a,b)
- #define sz(c) (int)(c).size()
- using namespace std;
- int h , w , ch , cw , dh , dw , dp[N][N] , ans = INF;
- char a[N][N];
- int movex[] = {1 , 0 , -1 , 0};
- int movey[] = {0 , 1 , 0 , -1};
- queue < pair<int,int> > q;
- bool check(int x , int y){
- if(x < 0 || y < 0) return 0;
- if(x >= h || y >= w) return 0;
- return 1;
- }
- int main(){
- cin >> h >> w;
- cin >> ch >> cw;
- cin >> dh >> dw;
- dh--; dw--;
- ch--; cw--;
- for(int i = 0 ; i < h ; i++){
- for(int j = 0 ;j < w ; j++) cin >> a[i][j];
- }
- for(int i = 0 ; i < h ; i++){
- for(int j = 0 ; j < w ; j++){
- dp[i][j] =INF;
- }
- }
- dp[ch][cw] = 0;
- q.push(mkp(ch,cw));
- while(sz(q) > 0){
- pair<int,int> p = q.front();
- int x = p.first , y = p.second;
- q.pop();
- for(int i = x-2 ; i <= x + 2 ; i++){
- for(int j = y-2 ; j <= y+2 ; j++){
- if(!check(i,j)) continue;
- int d = abs(i-x) + abs(j-y) <= 1 ? 0 : 1;
- if(a[i][j]=='.' && dp[i][j]>dp[x][y]+d) {
- dp[i][j] = dp[x][y] + d;
- q.push(mkp(i,j));
- }
- }
- }
- }
- if(dp[dh][dw] == INF) cout <<"-1";
- else cout << dp[dh][dw] << '\n';
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement