[shkola] Re: typi wyprosi i oshte po-typo predstavqne

From: Bono Nonchev <madcow@xxxxxx>
To: shkola@xxxxxxxxxxxxx
Date: Mon, 24 Nov 2003 11:32:46 +0200 (EET)
veche kogato vidq v pyrviq red desetoklasnici, bychvarova i t.n. triq. i na men 
mi omryzna, a nai veche zashtoto ivo e prav, i samo se opravdava. a nie mai 
nishto ne napravihme. prashtam vi debugnatoto reshenie, tova, koeto TRQBVASHE 
da predam, no ne mojah da napisha. moje da e N^4, ama shtqha da dadat pone 30 
t, pyk i bez piramida po-malko nqma kak da stane. malko me e qd.
nishto, sega da se sysredotochim v sledvashtoto systezanie - zimnoto. 

//chase

#include "iostream.h"
#include "conio.h"
#include "stdlib.h"
//#include "stdio.h"

#define MAXVALUE 100000
#define min(a,b) ((a)<(b)?(a):(b))
#define swap(a,b) {temp=a;a=b;b=temp;}

int M,N,K,DS;
int bf[100][100];
int al[50][2];
int distg[10000], visg[10000];
int dist[10000], vis[10000];
int lastmanstanding=0;

int gj(int a)
{return a%M;}

int gi(int a)
{return a/M;}

int gc(int i, int j)
{return i*M+j;}

int price(int a)
{return bf[gi(a)][gj(a)];}

int adj(int a, int b)
{
        int i1=gi(a), j1=gj(a), i2=gi(b), j2=gj(b);
        if(bf[i1][j1]==MAXVALUE||bf[i2][j2]==MAXVALUE)
                return MAXVALUE;
        else if((i1%2)==0)
        {
                
if((i1==(i2+1)&&j1==(j2+1))||(i1==(i2+2)&&j1==(j2))||(i1==(i2+1)&&j1==(j2))||
                   
(i1==(i2-1)&&j1==(j2))||(i1==(i2-2)&&j1==(j2))||(i1==(i2-1)&&j1==(j2+1)))
                   return bf[i1][j1];
        }
        else
        {
                
if((i1==(i2+1)&&j1==(j2))||(i1==(i2+2)&&j1==(j2))||(i1==(i2+1)&&j1==(j2-1))||
                   
(i1==(i2-1)&&j1==(j2-1))||(i1==(i2-2)&&j1==(j2))||(i1==(i2-1)&&j1==(j2)))
                   return bf[i1][j1];
        }
        return MAXVALUE;
}

void dijkstra(int a)
{
        int i;
        for(i=0;i<DS;i++)
        {
                dist[i]=adj(a,i);
                vis[i]=0;
        }
        dist[a]=0;
        vis[a]=1;
        int mindist, u;
        while(1)
        {
                mindist=MAXVALUE;
                for(i=0;i<DS;i++)
                        if(!vis[i]&&dist[i]<mindist)
                        {
                                mindist=dist[i];
                                u=i;
                        }
                if(mindist==MAXVALUE) break;
                vis[u]=1;
                for(i=0;i<DS;i++)
                        dist[i]=min(dist[i], dist[u]+adj(u,i));         
        }
}

void dijkstrag(int a)
{
        int i;
        for(i=0;i<DS;i++)
        {
                distg[i]=(price(a)<=dist[a] ? adj(a,i) : MAXVALUE);
                visg[i]=0;
        }
        distg[a]=0;
        visg[a]=1;
        int mindist, u;
        while(1)
        {
                mindist=MAXVALUE;
                for(i=0;i<DS;i++)
                        if(!visg[i]&&distg[i]<mindist)
                        {
                                mindist=distg[i];
                                u=i;
                        }
                if(mindist==MAXVALUE) break;
                visg[u]=1;
                if(dist[u]<(mindist+price(u))) 
                        {distg[i]=MAXVALUE;continue;}
                for(i=0;i<DS;i++)
                {
                        distg[i]=min(distg[i], distg[u]+adj(u,i));
                }
        }
}

void dijkstral()
{
        int i,j;
        for(i=0;i<DS;i++)
        {
                dist[i]=MAXVALUE;
                vis[i]=0;
        }
        for(j=0;j<K;j++)
        {
                for(i=0;i<DS;i++)
                {
                        dist[i]=min(dist[i], adj(gc(al[j][0], al[j][1]),i));
                }
                vis[gc(al[j][0], al[j][1])]=1;
                dist[gc(al[j][0], al[j][1])]=0;
        }
        int mindist, u;
        while(1)
        {
                mindist=MAXVALUE;
                for(i=0;i<DS;i++)
                        if(!vis[i]&&dist[i]<mindist)
                        {
                                mindist=dist[i];
                                u=i;
                        }
                if(mindist==MAXVALUE) break;
                vis[u]=1;
                for(i=0;i<DS;i++)
                        dist[i]=min(dist[i], dist[u]+adj(u,i));         
        }
}

int main()
{
        int i,j,x,y;
        char c[100];
        cin>>N>>M>>K;
        DS=M*N;
        for(i=0;i<100;i++)
                for(j=0;j<100;j++)
                        bf[i][j]=MAXVALUE;
        for(i=0;i<N;i++)
        {
                cin>>c;
                for(j=0;j<M;j++)
                        if(c[j]!='X')
                                bf[i][j]=c[j]-'0';
        }
        cin>>x>>y;
        x--;
        y--;
        for(i=0;i<K;i++)
        {
                cin>>al[i][0]>>al[i][1];
                al[i][0]--;
                al[i][1]--;
        }
        dijkstral();
        dijkstrag(gc(x,y));
        lastmanstanding=0;
        for(i=0;i<DS;i++)
                if(distg[i]!=MAXVALUE&&lastmanstanding<dist[i])
                        lastmanstanding=dist[i];
        cout<<lastmanstanding;
        return 0;
}



-----------------------------------------------------------------
http://www.sosbg.org - Направете още едно дете щастливо - 0881722 -  за тях!
[shkola] Re: typi wyprosi i oshte po-typo predstavqne

Other related posts:
