Pagini recente » Cod sursa (job #1032172) | Cod sursa (job #2414470)
#include<bits/stdc++.h>
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int N, M, is, js, ifin, jfin;
int dp[505][505][8];
int di[] = { -1, -1, +0, +1, +1, +1, +0, -1 };
int dj[] = { +0, +1, +1, +1, +0, -1, -1, -1 };
bool f[505][505][8], a[505][505];
queue< pair< pair<int,int>, int > > dq;
inline bool inmat( int i, int j ){
if( 1 <= i && i <= N && 1 <= j && j <= M )
return true;
return false;
}
int main(){
fin >> N >> M;
fin >> is >> js >> ifin >> jfin;
for( int i = 1; i <= N; i++ )
for( int j = 1; j <= M; j++ )
fin >> a[i][j];
memset( dp, 0x3f3f3f3f, sizeof(dp) );
for( int d = 0; d <= 7; d++ ){
dp[is][js][d] = 0;
f[is][js][d] = true;
dq.push( { {is, js}, d } );
}
while( !dq.empty() ){
int ic = dq.front().first.first;
int jc = dq.front().first.second;
int dir = dq.front().second;
dq.pop();
int iv, jv, new_dir;
///mentin directia
iv = ic + di[dir];
jv = jc + dj[dir];
if( inmat( iv, jv ) == true && a[iv][jv] == false && dp[iv][jv][dir] > dp[ic][jc][dir] ){
dp[iv][jv][dir] = dp[ic][jc][dir];
if( f[iv][jv][dir] == false )
f[iv][jv][dir] = true, dq.push( { {iv, jv}, dir } );
}
///mutare la stanga cu 45 grade
new_dir = ( ( dir == 0 ) ? 7 : (dir - 1) );
if( dp[ic][jc][new_dir] > dp[ic][jc][dir] + 1 ){
dp[ic][jc][new_dir] = dp[ic][jc][dir] + 1;
if( f[ic][jc][new_dir] == false )
f[ic][jc][new_dir] = true, dq.push( { {ic, jc}, new_dir } );
}
///mutare la dreapta cu 45 grade
new_dir = ( ( dir == 7 ) ? 0 : (dir + 1) );
if( dp[ic][jc][new_dir] > dp[ic][jc][dir] + 1 ){
dp[ic][jc][new_dir] = dp[ic][jc][dir] + 1;
if( f[ic][jc][new_dir] == false )
f[ic][jc][new_dir] = true, dq.push( { {ic, jc}, new_dir } );
}
f[ic][jc][dir] = false;
}
int ans = 0x3f3f3f3f;
for( int d = 0; d <= 7; d++ )
ans = min( ans, dp[ifin][jfin][d] );
ans = ( ans == 0x3f3f3f3f ) ? -1 : ans;
fout << ans << endl;
return 0;
}