Pagini recente » Cod sursa (job #2349262) | Cod sursa (job #2795171) | Cod sursa (job #2050473) | Cod sursa (job #269010) | Cod sursa (job #2523676)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "car.in" );
ofstream fout( "car.out" );
const int NMAX = 505;
const int INF = 200000000;
int N, M;
int dp[8][NMAX][NMAX];
int mat[NMAX][NMAX];
int l1, c1, l2, c2;
int dl[8] = { -1, -1, -1, 0, 1, 1, 1, 0 };
int dc[8] = { -1, 0, 1, 1, 1, 0, -1, -1 };
deque < pair< int,int > > Q;
void Read()
{
fin >> N >> M;
fin >> l1 >> c1 >> l2 >> c2;
for( int i = 1; i <= N; ++i )
for( int j = 1; j <= M; ++j )
fin >> mat[i][j];
}
int Cost( int dir1, int dir2 )
{
int ans = abs( dir1 - dir2 );
if( ans < 5 ) return ans;
return ans - ( 8 - ans );
}
void Do()
{
int L, C, lv, cv;
for( int i = 0; i <= N + 1; ++i )
mat[i][0] = mat[i][M + 1] = 1;
for( int j = 0; j <= M + 1; ++j )
mat[0][j] = mat[N + 1][j] = 1;
Q.push_back( { l2, c2 } );
while( !Q.empty() ) {
L = Q.front().first;
C = Q.front().second;
Q.pop_front();
//fout << L << ' ' << C << '\n';
for( int i = 0; i < 8; ++i )
{
lv = L + dl[i];
cv = C + dc[i];
if( mat[lv][cv] == 0 ) {
Q.push_back( { lv, cv });
mat[lv][cv] = 2;
}
else
if( mat[lv][cv] == 3 )
for( int j = 0; j < 8; ++j )
dp[j][L][C] = dp[i][lv][cv] + Cost( j, i );
}
mat[L][C] = 3;
if( L == l1 && C == c1 ) break;
}
/*for( int i = 0; i < 8; ++i )
fout << i << ' ' << dp[i][2][4] << '\n';
for( int i = 0; i < 8; ++i )
fout << i << ' ' << dp[i][3][5] << '\n';*/
int best_dp = INF;
for( int i = 0; i < 8; ++i )
best_dp = min( best_dp, dp[i][l1][c1] );
fout << best_dp << '\n';
}
int main()
{
Read();
Do();
return 0;
}