Cod sursa(job #56297)

Utilizator peanutzAndrei Homorodean peanutz Data 29 aprilie 2007 12:21:23
Problema Subsir Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#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;
}