Poj Solution 2049

http://poj.org/problem?id=2049

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#define INF 30000
#define NMAX 201
int a[NMAX][NMAX];
int map[NMAX][NMAX][4];
int yp[4]={1,0,-1,0},xp[4]={0,1,0,-1};
int M,N;
int x,y,d,t;
void init()
{
    for(int i=0;i<=200;i++)
    {
        map[0][i][2]=-1;
        map[200][i][0]=-1;
        map[i][0][3]=-1;
        map[i][200][1]=-1;
    }
}
typedef struct 
{
    int y,x;
}DATA;
DATA que[NMAX*NMAX*100];
long front,end;
int enque(int y,int x)
{
    que[end].y=y;
    que[end].x=x;
    end++;
    return 1;
}
void HeapAdjust(int s,int m);
int deque(int &y,int &x)
{
    HeapAdjust(1,end-1);
    if(front==end)
    {
        y=0;
        x=0;
        return 0;
    }
    y=que[front].y;
    x=que[front].x;
    end--;
    DATA t;
    t=que[end];
    que[end]=que[front];
    que[front]=t;
    
    return 1;
}
void HeapAdjust(int s,int m)
{
    DATA rc;
    rc.x=que[s].x;
    rc.y=que[s].y;
    for(int j=2*s;j<=m;j*=2)
    {
        if(j<m&&a[que[j].y][que[j].x]>a[que[j+1].y][que[j+1].x])
            ++j;
        if(a[rc.y][rc.x]<=a[que[j].y][que[j].x])
            break;
        que[s]=que[j];
        s=j;
    }
    que[s].x=rc.x;
    que[s].y=rc.y;
}

void set(int v)
{
    int i;
    if(d==0)
    {
        for(i=x;i<x+t;i++)
        {
            map[y][i][2]=v;
            map[y-1][i][0]=v;
        }
    }
    else
    {
        for(i=y;i<y+t;i++)
        {
            map[i][x][3]=v;
            map[i][x-1][1]=v;
        }
    }
}
void solve()
{
    front=end=0;
    enque(0,0);
    a[0][0]=0;
    int cy,cx,p;
    while(deque(cy,cx))
    {
        for(p=0;p<4;p++)
        {
            if(map[cy][cx][p]!=-1)
            {
                if(a[cy+yp[p]][cx+xp[p]]>map[cy][cx][p]+a[cy][cx]||a[cy+yp[p]][cx+xp[p]]==-1)
                {
                    a[cy+yp[p]][cx+xp[p]]=map[cy][cx][p]+a[cy][cx];
                    enque(cy+yp[p],cx+xp[p]);
                }
            }
        }
        
    }

}    
int main()
{

#if debug     
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    int i;
    float ex,ey;
    scanf("%d%d",&M,&N);
    while(M!=-1)
    {
        memset(map,0,sizeof(map));
        memset(a,0xff,sizeof(a));
        init();
        for(i=0;i<M;i++)
        {    
            scanf("%d%d%d%d",&x,&y,&d,&t);
            set(-1);
        }
        for(i=0;i<N;i++)
        {    
            scanf("%d%d%d",&x,&y,&d);
            t=1;
            set(1);
        }
        scanf("%f%f",&ex,&ey);
        if(ex>=200||ey>=200)
        {
            printf("0n");
        }
        else
        {
            solve();
            if(a[(int)ey][(int)ex]!=-1)
                printf("%dn",a[(int)ey][(int)ex]);
            else
                printf("-1n");
        }
        scanf("%d%d",&M,&N);
    }
        
#if debug
    fclose(stdin);
    fclose(stdout);
#endif
    return 1;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *