Nu exista pagina, dar poti sa o creezi ...
Cod sursa(job #49690)
Utilizator | Data | 6 aprilie 2007 11:18:11 | |
---|---|---|---|
Problema | Car | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.33 kb |
#include <stdio.h>
#include <math.h>
#include <stack>
#define NMAX 505
#define INF 1666666
#define DMAX 8
using namespace std;
stack<int> L[3];
int N, M, A[NMAX][NMAX], D[NMAX][NMAX][8], C, SL, SC, FL, FC;
int X[DMAX] = {1, 1, 0,-1,-1,-1, 0, 1}; //linie
int Y[DMAX] = {0, 1, 1, 1, 0,-1,-1,-1}; //coloana
int cost[DMAX][DMAX];
void expand(int nod)
{
int i, j, dir, x, k;
int ii, jj;
dir = nod >> 18;
j = (nod & 511);
i = (nod >> 9) & 511;
for (k = 0; k < DMAX; k++)
if (cost[k][dir] < 3)
if ((A[i+X[k]][j+Y[k]] == 0) && (D[i+X[k]][j+Y[k]][dir] > (C+cost[k][dir])))
{
ii = i+X[k];
jj = j+Y[k];
D[ii][jj][dir] = C+cost[k][dir];
x = (ii << 9) + jj + (k << 18);
L[ (C+cost[k][dir])%3 ].push(x);
}
}
int main()
{
int i, j, x = 0, k, min, d, t, nod;
freopen("car.in", "r", stdin);
scanf("%d %d", &N, &M);
scanf("%d %d %d %d", &SL, &SC, &FL, &FC);
for (i = 0; i < DMAX; i++)
for (j = i+1; j < DMAX; j++)
{
x = j-i;
if (x > 4) x = 8-x;
cost[i][j] = cost[j][i] = x;
}
for (i = 0; i < NMAX; i++)
for (j = 0; j < NMAX; j++) A[i][j] = 1;
for (i = 0; i <= N; i++)
for (j = 0; j <= M; j++)
for (d = 0; d < DMAX; d++) D[i][j][d] = INF;
for (d = 0; d < DMAX; d++) D[SL][SC][d] = 0;
for (i = 1; i <= N; i++)
for (j = 1; j <= M; j++) scanf("%d", &A[i][j]);
for (i = 0; i < DMAX; i++)
L[0].push((SL << 9) + SC + (i << 18));
while (L[0].size()+L[1].size()+L[2].size() > 0)
{
t = C%3;
while (L[t].size() > 0)
{
nod = L[t].top();
L[t].pop();
expand(nod);
}
C++;
}
min = D[FL][FC][0];
for (d = 1; d < 8; d++)
if (min > D[FL][FC][d]) min = D[FL][FC][d];
if (min == INF) min = -1;
freopen("car.out", "w", stdout);
printf("%d\n", min);
return 0;
}