Pagini recente » Cod sursa (job #322152) | Cod sursa (job #537648) | Cod sursa (job #2820608)
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;
ifstream fin("car.in");
ofstream fout("car.out");
int a[10][10], n, m, xs, ys, xf, yf;
int c[505][505], d[8][505][505];
queue <pair < int, int > > Q;
int dx[] = { 1,1,0,-1,-1,-1,0,1 };
int dy[] = { 0,-1,-1,-1,0,1,1,1 };
bool OK(int i, int j)
{
return (1 <= i and i <= n and 1 <= j and j <= m);
}
int main()
{
int i, j, k, x, y, sol = -1, p;
for (i = 0; i <= 7; i++)
for (j = 0; j <= 7; j++)
a[i][j] = abs(i - j);
for (i = 0; i <= 7; i++)
for (j = 0; j <= 7; j++)
if (a[i][j] > 4) a[i][j] = 8 - a[i][j];
fin >> n >> m >> xs >> ys >> xf >> yf;
for (i = 1; i <= n; i++)
for (j = 1; j <= m; j++)
fin >> c[i][j];
for (i = 0; i <= 7; i++)
for (j = 1; j <= n; j++)
for (k = 1; k <= m; k++)
d[i][j][k] = INF;
for (i = 0; i <= 7; i++)
d[i][xs][ys] = 0;
Q.push({ xs,ys });
while (!Q.empty())
{
x = Q.front().first;
y = Q.front().second;
Q.pop();
for (k = 0; k <= 7; k++)
{
i = x + dx[k];
j = y + dy[k];
if (OK(i, j) and c[i][j] == 0)
for (p = 0; p <= 7; p++)
{
if (d[k][x][y] + a[p][k] < d[p][i][j])
{
d[p][i][j] = d[k][x][y] + a[p][k];
Q.push({ i,j });
}
}
}
}
sol = INT_MAX;
for (i = 0; i <= 7; i++)
if (d[i][xf][yf] != INF)
sol = min(sol, d[i][xf][yf]);
fout << sol;
return 0;
}