Pagini recente » Cod sursa (job #2240311) | Cod sursa (job #2998721) | Cod sursa (job #695185) | Cod sursa (job #2506016) | Cod sursa (job #56297)
Cod sursa(job #56297)
#include <stdio.h>
#include <math.h>
#include <memory.h>
#define INFI -0x3f
#define NMAX 70
long double a[NMAX][NMAX], ef[NMAX][NMAX], len[NMAX][NMAX];
int n, m;
long double lmax;
int xi, yi, xf, yf;
typedef struct coada
{
int x, y;
};
coada c[NMAX*NMAX*NMAX];
/*void print_a(double a[NMAX][NMAX])
{
int i, j;
for(i = 0; i <= n+1; ++i)
{
for(j = 0; j <= m+1; ++j)
{
printf("%Lf ", a[i][j]);
}
printf("\n");
}
printf("\n");
}
*/
void read()
{
int i, j;
scanf("%d %d\n", &n, &m);
scanf("%Lf\n", &lmax);
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= m; ++j)
{
scanf("%Lf ", &a[i][j]);
}
scanf("\n");
}
scanf("%d %d %d %d\n", &xi, &yi, &xf, &yf);
}
void bordare()
{
int i;
for(i = 0; i <= n+1; ++i)
a[i][0] = a[i][m+1] = INFI;
for(i = 0; i <= m+1; ++i)
a[0][i] = a[n+1][i] = INFI;
}
void solve()
{
int x, y, i, j;
int inc, sf;
int nextx, nexty;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
long double d;
long double dist;
inc = sf = 0;
c[0].x = xi;
c[0].y = yi;
/*
for(i = 0; i <= n; ++i)
{
for(j = 0; j <=m; ++j)
ef[i][j] = -10000;
}*/
ef[xi][yi] = 0;
while(inc <= sf)
{
x = c[inc].x;
y = c[inc++].y;
for(i = 0; i < 4; ++i)
{
nextx = x + dx[i];
nexty = y + dy[i];
if(a[nextx][nexty] == INFI)
continue;
//printf("%d %d\n", nextx, nexty);
d = sqrtl((a[x][y]-a[nextx][nexty])*(a[x][y]-a[nextx][nexty])+1);
dist = d;
d = floor(dist) * dist;
/*if(floor(dist) == 0)
d = dist; */
if(len[x][y] + dist > lmax)
continue;
if(floor(dist) != 0 && a[x][y] > a[nextx][nexty])
{ if(d!=0)
d /= 2;
}
/*else if(floor(dist) == 0 && a[x][y] > a[nextx][nexty])
{
d = dist;
} */
else if(a[x][y] == a[nextx][nexty])
{
d = 1;
}
if((ef[nextx][nexty] == 0) || (ef[x][y] + d < ef[nextx][nexty]) || (ef[x][y] + d == ef[nextx][nexty] && len[x][y]+dist < len[nextx][nexty]))
{
ef[nextx][nexty] = ef[x][y] + d;
len[nextx][nexty] = len[x][y] + dist;
c[++sf].x = nextx;
c[sf].y = nexty;
}
}
}
}
int main()
{
freopen("excursie.in", "r", stdin);
freopen("excursie.out", "w", stdout);
read();
bordare();
solve();
/*
print_a(a);
print_a(ef);
print_a(len);
*/
printf("%.3Lf %.3Lf\n", ef[xf][yf], len[xf][yf]);
fclose(stdin);
fclose(stdout);
return 0;
}