Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #define N 200
- using namespace std ;
- int n , m , x_start , y_start , x_end , y_end , cont = 0 , x[20000] , y[20000] ;
- bool check = 1 , check_lo[N][N] ;
- class loc
- {
- public :
- bool can_walk , prev = false ;
- int dis = -1 ;
- };
- loc lo[N][N] ;
- loc lo_2[N][N] ;
- main ()
- {
- ios_base::sync_with_stdio(false);
- int count = 1 ;
- cin >> n >> m >> x_start >> y_start >> x_end >> y_end ;
- for ( int i = 1 ; i <= n ; i ++ )
- {
- for ( int j = 1 ; j <= m ; j ++ )
- {
- cin >> lo[i][j].can_walk ;
- lo_2[i][j].can_walk = lo[i][j].can_walk ;
- }
- }
- lo[x_start][y_start].prev = 1 ;
- lo[x_start][y_start].dis = 1 ;
- lo_2[x_end][y_end].prev = 1 ;
- lo_2[x_end][y_end].dis = 1 ;
- while ( check )
- {
- check = 0 ;
- for ( int i = 1 ; i <= n ; i ++ )
- {
- for ( int j = 1 ; j <= m ; j ++ )
- {
- if ( lo[i][j].prev == 1 )
- {
- check = 1 ;
- if ( ( lo[i+1][j].dis > lo[i][j].dis + 1 || lo[i+1][j].dis == -1 ) )
- {
- if ( lo[i+1][j].can_walk )
- {
- lo[i+1][j].dis = lo[i][j].dis + 1 ;
- lo[i+1][j].prev = 1 ;
- }
- else
- {
- lo[i+1][j].dis = -2 ;
- }
- }
- if ( ( lo[i-1][j].dis > lo[i][j].dis + 1 || lo[i-1][j].dis == -1 ) )
- {
- if ( lo[i-1][j].can_walk )
- {
- lo[i-1][j].dis = lo[i][j].dis + 1 ;
- lo[i-1][j].prev = 1 ;
- }
- else
- {
- lo[i-1][j].dis = -2 ;
- }
- }
- if ( ( lo[i][j+1].dis > lo[i][j].dis + 1 || lo[i][j+1].dis == -1 ) )
- {
- if ( lo[i][j+1].can_walk )
- {
- lo[i][j+1].dis = lo[i][j].dis + 1 ;
- lo[i][j+1].prev = 1 ;
- }
- else
- {
- lo[i][j+1].dis = -2 ;
- }
- }
- if ( ( lo[i][j-1].dis > lo[i][j].dis + 1 || lo[i][j-1].dis == -1 ) )
- {
- if ( lo[i][j-1].can_walk )
- {
- lo[i][j-1].dis = lo[i][j].dis + 1 ;
- lo[i][j-1].prev = 1 ;
- }
- else
- {
- lo[i][j-1].dis = -2 ;
- }
- }
- lo[i][j].prev = 0 ;
- }
- }
- }
- }
- check = 1 ;
- while ( check )
- {
- check = 0 ;
- for ( int i = 1 ; i <= n ; i ++ )
- {
- for ( int j = 1 ; j <= m ; j ++ )
- {
- if ( lo_2[i][j].prev == 1 )
- {
- check = 1 ;
- if ( ( lo_2[i+1][j].dis > lo_2[i][j].dis + 1 || lo_2[i+1][j].dis == -1 ) )
- {
- if ( lo_2[i+1][j].can_walk )
- {
- lo_2[i+1][j].dis = lo_2[i][j].dis + 1 ;
- lo_2[i+1][j].prev = 1 ;
- }
- else
- {
- lo_2[i+1][j].dis = -2 ;
- }
- }
- if ( ( lo_2[i-1][j].dis > lo_2[i][j].dis + 1 || lo_2[i-1][j].dis == -1 ) )
- {
- if ( lo_2[i-1][j].can_walk )
- {
- lo_2[i-1][j].dis = lo_2[i][j].dis + 1 ;
- lo_2[i-1][j].prev = 1 ;
- }
- else
- {
- lo_2[i-1][j].dis = -2 ;
- }
- }
- if ( ( lo_2[i][j+1].dis > lo_2[i][j].dis + 1 || lo_2[i][j+1].dis == -1 ) )
- {
- if ( lo_2[i][j+1].can_walk )
- {
- lo_2[i][j+1].dis = lo_2[i][j].dis + 1 ;
- lo_2[i][j+1].prev = 1 ;
- }
- else
- {
- lo_2[i][j+1].dis = -2 ;
- }
- }
- if ( ( lo_2[i][j-1].dis > lo_2[i][j].dis + 1 || lo_2[i][j-1].dis == -1 ) )
- {
- if ( lo_2[i][j-1].can_walk )
- {
- lo_2[i][j-1].dis = lo_2[i][j].dis + 1 ;
- lo_2[i][j-1].prev = 1 ;
- }
- else
- {
- lo_2[i][j-1].dis = -2 ;
- }
- }
- lo_2[i][j].prev = 0 ;
- }
- }
- }
- }
- for ( int i = 1 ; i <= n ; i ++ )
- {
- for ( int j = 1 ; j <= m ; j ++ )
- {
- if ( lo[i][j].dis == lo_2[i][j].dis && lo[i][j].dis == -2 )
- {
- x[cont] = i ;
- y[cont] = j ;
- cont ++ ;
- }
- }
- }
- int min_1 = 999999 ;
- for ( int i = 0 ; i < cont ; i ++ )
- {
- for ( int a = -1 ; a <= 1 ; a += 2 )
- {
- for ( int b = -1 ; b <= 1 ; b += 2 )
- {
- if ( lo[ x[i] + a ][ y[i] ].dis > 0 && lo_2[ x[i] + b ][ y[i] ].dis > 0 )
- {
- if ( lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] + b ][ y[i] ].dis < min_1 )
- {
- min_1 = lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] + b ][ y[i] ].dis ;
- }
- }
- if ( lo[ x[i] + a ][ y[i] ].dis > 0 && lo_2[ x[i] ][ y[i] + b ].dis > 0 )
- {
- if ( lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] ][ y[i] + b ].dis < min_1 )
- {
- min_1 = lo[ x[i] + a ][ y[i] ].dis + lo_2[ x[i] ][ y[i] + b ].dis ;
- }
- }
- if ( lo[ x[i] ][ y[i] + a ].dis > 0 && lo_2[ x[i] + b ][ y[i] ].dis > 0 )
- {
- if ( lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] + b ][ y[i] ].dis < min_1 )
- {
- min_1 = lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] + b ][ y[i] ].dis ;
- }
- }
- if ( lo[ x[i] ][ y[i] + a ].dis > 0 && lo_2[ x[i] ][ y[i] + b ].dis > 0 )
- {
- if ( lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] ][ y[i] + b ].dis < min_1 )
- {
- min_1 = lo[ x[i] ][ y[i] + a ].dis + lo_2[ x[i] ][ y[i] + b ].dis ;
- }
- }
- }
- }
- }
- cout << cont << endl << min_1 + 1 ;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement