[shkola] zad A2 - reshenie - shkola

[shkola] zad A2 - reshenie

From: Bono Nonchev <madcow@xxxxxx>
To: shkola@xxxxxxxxxxxxx
Date: Mon, 24 Nov 2003 01:17:22 +0200 (EET)
eto reshenieto na chase-a.
ne sym iztril izlishniq kod kato void dijkstra(int a), obache vqrvam che raboti 
vqrno... pone testoviq primer hvana. utre shte si poigraq da navra i piramida. 
inache mai mnojko funkcii sym pisal. za okolo 2 chasa go napisah dotuk?!
da ne vi pravi vpechatlenie izhoda. gledaite samo poslednoto chislo. 
slojnostta, uvi, e N^4. 

//chase

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

#define MAXVALUE 100000
#define min(a,b) ((a)<(b)?(a):(b))

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;

// heap[10000];

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;
}

/*int ttreach(int distv, int v)
{
        return ((distv+price(v)<=dist[v]) ? distv : 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]=(adj(a,i)<=dist[a] ? adj(a,i) : MAXVALUE);
                visg[i]=0;
        }
        distg[a]=0;
        visg[a]=1;
        int mindist, u, tdist;
        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;
                for(i=0;i<DS;i++)
                {
                        tdist=min(distg[i], distg[u]+adj(u,i));
                        
if(lastmanstanding<dist[i]&&dist[i]!=MAXVALUE&&tdist!=MAXVALUE)
                                lastmanstanding=dist[i];
                        distg[i]=(tdist<=dist[i]? tdist : MAXVALUE);
                }
        }
}

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]--;
        }

        for(i=0;i<DS;i++)
        {
                for(j=0;j<DS;j++)
                        cout<<(adj(i,j)==MAXVALUE ? 0 : adj(i,j))<<' ';
                cout<<'\n';
        }
    dijkstra(gc(al[0][0],al[0][1]));
        cout<<'\n';
        for(i=0;i<DS;i++)
                cout<<dist[i]<<' ';
    dijkstra(gc(al[1][0],al[1][1]));
        cout<<'\n';
        for(i=0;i<DS;i++)
                cout<<dist[i]<<' ';
        dijkstral();
        cout<<'\n';
        for(i=0;i<DS;i++)
                cout<<dist[i]<<' ';
        dijkstrag(gc(x,y));
        cout<<'\n';
        for(i=0;i<DS;i++)
                cout<<distg[i]<<' ';
        cout<<'\n';
        /////////////////////////////
        cout<<lastmanstanding;
        return 0;
}

-----------------------------------------------------------------
http://www.sosbg.org - Направете още едно дете щастливо - 0881722 -  за тях!
[shkola] zad A2 - reshenie

Other related posts:
