Shiam7777777

Untitled

Mar 4th, 2019
119
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.93 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fast ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  4. #define ll long long
  5. #define ld double
  6. #define llu long long unsigned
  7. int ans = INT_MAX;
  8. int d[60][60];
  9.  
  10. int dist( int a , int b , int x , int y )
  11. {
  12.     return pow( abs(a - x) , 2 ) + pow( abs(b - y) , 2 );
  13. }
  14.  
  15. vector < pair < int , int > > ini;
  16. vector < pair < int , int > > des;
  17.  
  18. void bfs( int x , int y )
  19. {
  20.     if( d[x][y] == 0 && x > -1 && y > -1 )
  21.     {
  22.         ini.push_back( make_pair( x , y ) );
  23.         d[x][y] = -1;
  24.         bfs(  x-1 ,  y );
  25.         bfs(  x+1 ,  y );
  26.         bfs(  x ,  y+1 );
  27.         bfs(  x ,  y-1 );
  28.     }
  29.     else
  30.         return;
  31. }
  32.  
  33. void bfs1( int x , int y )
  34. {
  35.     if( d[x][y] == 0 && x > -1 && y > -1 )
  36.     {
  37.         des.push_back( make_pair( x , y ) );
  38.         d[x][y] = -1;
  39.         bfs1(  x-1 ,  y );
  40.         bfs1(  x+1 ,  y );
  41.         bfs1(  x ,  y+1 );
  42.         bfs1(  x ,  y-1 );
  43.  
  44.     }
  45.     else
  46.         return;
  47. }
  48.  
  49. int main()
  50. {
  51.     fast;
  52.     memset( d , -1 , sizeof( d ) );
  53.     int n;
  54.     cin>>n;
  55.     int ix , iy;
  56.     cin>>ix>>iy;
  57.     int dx , dy;
  58.     cin>>dx>>dy;
  59.     for( int i = 0 ; i < n ; i++ )
  60.     {
  61.         string s;
  62.         cin>>s;
  63.         for( int j = 0 ; j < n ; j++ )
  64.             d[i][j] = s[j] - '0';
  65.     }
  66. //    for( int i = 0 ; i < n ; i++ )
  67. //    {
  68. //        for( int j = 0 ; j < n ; j++ )
  69. //            cout<<d[i][j]<<" ";
  70. //        cout<<endl;
  71. //    }
  72.     bfs( ix-1 , iy-1 );
  73.     if( d[dx-1][dy-1] == -1 )
  74.     {
  75.         cout<<0<<endl;
  76.         return 0;
  77.     }
  78.     bfs1( dx-1 , dy-1 );
  79.     if( ix == dx && iy == dy )
  80.     {
  81.         cout<<0<<endl;
  82.         return 0;
  83.     }
  84.     for( int i = 0 ; i < ini.size() ; i++ )
  85.         for( int j = 0 ; j < des.size() ; j++ )
  86.         {
  87.             ans = min( dist( ini[i].first , ini[i].second , des[j].first , des[j].second ) , ans );
  88.         }
  89.     cout<<ans<<endl;
  90.     return 0;
  91. }
Advertisement
Add Comment
Please, Sign In to add comment