Denis' Solution 2C: Hoppers

This is the personal work of Denis Dmitriev; it is not an officially verified or endorsed solution.

Denis writes: This problem is probably the only interesting one amongst all the 1996 Stage 2 problems. It is not purely technical, and it is not directly based on some kind of a well-known algorithm. However, it can be solved pretty much easily using the technique called `dynamic programming'. The general idea is to keep for each point of the field the number of steps in which it can be reached, and to make all the possible `hops' from all the points, reached the moment before, on each iteration. But since `hopper' may reach the same point with different velocities (and we can't know in advance which velocity will help it to reach the destination) we have to keep these numbers of hops separated by velocities. Since hopper may have only seven possible speed variations in each direction, the total number of its states is equal to 49. Therefore the size of the table required is 50176 bytes (on 32-bit machine). That is bearable. -DD

C++ Source Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int dx[9]={0,1,1,0,-1,-1,-1,0,1};
int dy[9]={0,0,1,1,1,0,-1,-1,-1};

/* derive velocities (dx,dy) from the index */
#define COMPUTE_DX(index)       ((index)%7-3)
#define COMPUTE_DY(index)       ((index)/7-3)

/* packs velocity (dx,dy) */
#define MAKE_INDEX(dx,dy)       (((dx)+3)+7*((dy)+3))

/* field size */
int h,w;

/* tries to make a hop from the specified point (x,y) with a new velocity
 * (dx,dy) */
bool make_hop(int field[16][16][49],int x,int y,int f,int dx,int dy)
{
    int nx=x+dx,ny=y+dy;

    /* if the velocity exceeds the limit, or if the hop will make the
     * hopper to jump outside the boundaries, or if it is a zero-jump,
     * the
     * hop cannot be done
     */
    if(abs(dx)>3||abs(dy)>3||(nx==x&&ny==y)||nx<0||nx>=w||ny<0||ny>=h)
        return false;

    /* if the point we're trying to jump into is an obstacle or we've
     * been
     * at this point with exactly the same velocity earlier, the hop
     * cannot
     * be done
     */
    int &c=field[nx][ny][MAKE_INDEX(dx,dy)];
    if(c==-1)
        return false;
    if(c)
        if(f+1>=c)
            return false;

    /* make the hop */
    c=f+1;
    return true;
}

/* searches for the possible hops */
bool search(int field[16][16][49],int w,int h,int count)
{
    int i,j,l;
    bool did=false;

    /* for each point on the grid */
    for(i=0;i<w;i++)
    {
        for(j=0;j<h;j++)
        {
            /* and for each velocity possible */
            for(l=0;l<49;l++)
            {
                /* if the hopper has just been here */
                int &c=field[i][j][l];
                if(c==count)
                {
                    /* try to make all the possible hops
                     * */
                    int cdx=COMPUTE_DX(l);
                    int cdy=COMPUTE_DY(l);
                    for(int k=0;k<9;k++)
                        did|=make_hop(field,i,j,c,cdx+dx[k],cdy+dy[k]);
                }
            }
        }
    }

    /* if the hopper could do at least a single hop, return true */
    return did;
}

/* finds the minimal number of hops required to get to the given point
 * (field is expected to be completely and properly filled)
 */
int compute_row_value(int field[16][16][49],int x,int y)
{
    int m=-1;
    for(int i=0;i<49;i++)
    {
        int &nu=field[x][y][i];
        if(nu&&(m==-1||nu<m))
            m=nu;
    }
    return m;
}

void main(void)
{
    FILE *fp=fopen("hop.in","r");
    FILE *fo=fopen("hop.out","w");

    int ntests,c,x1,x2,y1,y2,no,i,j,k,m,ox1,ox2,oy1,oy2;
    fscanf(fp,"%d",&ntests);

    for(;ntests--;)
    {
        int field[16][16][49];
        memset(field,0,sizeof(field));

        fscanf(fp,"%d %d",&w,&h);
        fscanf(fp,"%d %d %d %d",&x1,&y1,&x2,&y2);
        fscanf(fp,"%d",&no);

        /* read the map (obstacles) */
        for(;no--;)
        {
            fscanf(fp,"%d %d %d %d",&ox1,&ox2,&oy1,&oy2);

            for(i=ox1;i<=ox2;i++)
                for(j=oy1;j<=oy2;j++)
                    for(k=0;k<49;k++)
                        field[i][j][k]=-1;
        }

        /* mark the starting point */
        field[x1][y1][MAKE_INDEX(0,0)]=1;

        /* `fill' the map */
        for(c=1;search(field,w,h,c++);) ;

        /* print the answer */
        if((m=compute_row_value(field,x2,y2))!=-1)
            fprintf(fo,"Optimal solution takes %d hops.\n",m-1);
        else
            fprintf(fo,"No solution.\n");
    }

    fclose(fo);
    fclose(fp);
}