Текущ брой на Списание ИнфоМан
 


USACO квалификационен кръг - октомври, GOLD Division, Задача cowski

Уловието на задачата може да прочетете тук.

Решение

За тази задача е важно наблюдението, че по какъвто и път да достигнем до дадена клетка скоростта, когато сме там, ще е винаги една и съща. Началната клетка е с координати (0,0)и началната скорост е V. За дадена клетка с координати (x,y)скоростта в нея ще еV*2H(0,0) - H(x,y). Тук H(x,y)показва височината на дадена клетка. По какъвто и път да минем, за да достигнем дадена клетка скоростта в нея ще е една и съща.

Така мрежата може да се представи като граф, в който всеки връх има максимално 4 излизащи от него ребра. За да се намери най-бързият път от горния ляв ъгъл до долния десен може да се използва алгоритъма на Дийкстра. Върховете в графа могат да бъдат максимално 10000, тъй като мрежата е с максимална големина 100x100. Следователно трябва да се използва пирамида при имплементацията на алгоритъма, за да се постигне по-добро време на изпълнение. Тогава сложността е O(M*logN), като Mе броят на ребрата, а Nса върховете в графа.

Примерна реализация


# include <stdio.h>
# include <float.h>
# include <math.h>
# include <stdlib.h>
# define MAXN 128
# define MAXH 64

long double sp;
long double dist[MAXN][MAXN]; //Min time required to reach.
char used[MAXN][MAXN];        //Is the min time callculated
int n,m,tb[MAXN][MAXN],h0;    //Number of Rows and Cowums, 
                              //heights, initial height
int indx[4] = {-1,0,1,0};     //Used for easy move left, up, right, down
int indy[4] = {0,1,0,-1};

struct node{
    int x,y;
};

node h[MAXN*MAXN];            //Heap
int hlen=0;                   //Heap len
int hpos[MAXN][MAXN];         //Position of an element in the heap

/* HEAP */
//Sifting a element up
void siftup(int p) {
    int pp = (p-1)/2;
    node buf = h[p];
    while ( p!=0 && dist[buf.x][buf.y] < 
		dist[h[pp].x][h[pp].y] ) {
	h[p] = h[pp];
	hpos[h[p].x][h[p].y] = p;
	p = pp;
	pp = (p-1)/2;
    }
    h[p] = buf;
    hpos[h[p].x][h[p].y] = p;
}

//Ads new element
void push(int a, int b) {
    h[hlen].x = a;
    h[hlen].y = b;
    hpos[a][b] = hlen;
    hlen++;
    if ( hlen>1 ) 
	siftup(hpos[a][b]);
}

//Sifting a element down
void siftdown(int p) {
    int pp=2*p+1;
    node buf=h[p];
    while ( pp+1<hlen && 
	      ( dist[h[pp].x][h[pp].y]<dist[buf.x][buf.y] || 
			dist[h[pp+1].x][h[pp+1].y]<dist[buf.x][buf.y] )) {
	if (  dist[h[pp].x][h[pp].y]<dist[h[pp+1].x][h[pp+1].y] ) {
	    h[p] = h[pp];
	    hpos[h[p].x][h[p].y] = p;
	    p = pp;
	    pp = 2*p+1;
	} else {
	    h[p] = h[pp+1];
	    hpos[h[p].x][h[p].y] = p;
	    p = pp+1;
	    pp = 2*p+1;
	}
    }
    while ( pp<hlen && dist[h[pp].x][h[pp].y]<dist[buf.x][buf.y] ) {
		h[p] = h[pp];
		hpos[h[p].x][h[p].y] = p;
		p = pp;
		pp = 2*p+1;
    }
    h[p] = buf;
    hpos[h[p].x][h[p].y] = p;    
}

//Get an element from the top of the Heap
node pop() {
    node res;
    if ( hlen==0 ) {
		res.x = n; res.y = m;
    } else {
		res = h[0];
		hpos[res.x][res.y] = -1;
	if ( hlen>1 ) {
	    h[0] = h[--hlen];
	    siftdown(0);
	}
    }
    return res;
}

/* END */


//Reads Input
void readf() {
    freopen("cowski.in","r",stdin);
    freopen("cowski.out","w",stdout);
    scanf("%llg %d %d",&sp,&n,&m);
    for ( int i=0 ; i<=n+1 ; i++ )
		for ( int j=0 ; j<=m+1 ; j++ )
		    tb[i][j] = 1000;
    for ( int i=1; i<=n ; i++ ) {
		for ( int j=1 ; j<=m ; j++ ) {
		    scanf("%d",&tb[i][j]);

		}
    }    
}

//Dijkstra Algorithm
long double dijkstra() {
	//Init
    for ( int i=0 ; i<MAXN ; i++ ) 
		for ( int j=0 ; j<MAXN ; j++ ) {
			dist[i][j] = LDBL_MAX;
			used[i][j] = 0;
			hpos[i][j] = -1;
		}
    h0 = tb[1][1];
    dist[1][1] = 0;
    used[1][1] = 1;
    int nextx,nexty,nexth;
    long double t;
    nextx = 1, nexty = 1, nexth = h0;
	//End of Init
    do {
	used[nextx][nexty] = 1;
	for ( int i=0 ; i<4 ; i++ ) {
	    if ( tb[nextx+indx[i]][nexty+indy[i]]==1000 ) 
			continue;
	    t = 1.0/(sp*pow(2.0,h0-tb[nextx][nexty]));
	    if ( used[nextx+indx[i]][nexty+indy[i]] == 0 && 
             dist[nextx+indx[i]][nexty+indy[i]] > 
             dist[nextx][nexty]+t ) {

			dist[nextx+indx[i]][nexty+indy[i]] = 
				dist[nextx][nexty]+t;
			if ( hpos[nextx+indx[i]][nexty+indy[i]]==-1 ) {
			    push(nextx+indx[i],nexty+indy[i]);
			} else {
			    siftup(hpos[nextx+indx[i]][nexty+indy[i]]);

			}	
	    }
	}
	node pp;
	pp = pop();
	nextx = pp.x; nexty = pp.y;
		
    }while( nextx!=n || nexty!=m);
    return dist[n][m];
}

int main() {
    readf();
    printf("%.2llf\n",dijkstra());

    return 0;
}



Автор: Никола Борисов


обратно към текущ брой