Cod sursa(job #418512)

Utilizator ZillaMathe Bogdan Zilla Data 15 martie 2010 22:45:58
Problema BFS - Parcurgere in latime Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 2.21 kb
#include <stdio.h>

#define mod 1048756
#define Nmax 1024
#define INF 1000000000

struct coada{
    int x,y;
};

coada q[Nmax*Nmax+1000];
int n,m,pl,pc,cl,cc,best[Nmax][Nmax],st,dr,dx[4]={-1,0,0,1},dy[4]={0,-1,1,0};
char tip[Nmax][Nmax],viz[Nmax][Nmax];

int main()
{
    int i,j;

    freopen("padure.in","r",stdin);
    freopen("padure.out","w",stdout);

    scanf("%d%d%d%d%d%d",&n,&m,&pl,&pc,&cl,&cc);

    for(i=1;i<=n;++i)
        for(j=1;j<=m;++j)
			{
				scanf("%d",&tip[i][j]);
				best[i][j]=INF;
			}

    for(i=1;i<=n;++i)
        best[i][0]=best[i][m+1]=-1;
    for(i=1;i<=m;++i)
        best[0][i]=best[n+1][i]=-1;

    best[pl][pc]=0;
    q[++dr].x=pl;
    q[dr].y=pc;

    while(st<=dr)
        {
            ++st;
            int x=q[st%mod].x;
            int y=q[st%mod].y;
            viz[x][y]=0;
            for(i=0;i<4;++i)
                {
                    if(tip[x+dx[i]][y+dy[i]]!=tip[x][y] && best[x+dx[i]][y+dy[i]]>best[x][y]+1)
                        {
                            best[x+dx[i]][y+dy[i]]=best[x][y]+1;
                            if(viz[x+dx[i]][y+dy[i]]);
                            else
                            {
                            viz[x+dx[i]][y+dy[i]]=1;
                            q[(++dr)%mod].x=x+dx[i];
                            q[dr%mod].y=y+dy[i];
                            }
                        }
                    else
                        if(tip[x+dx[i]][y+dy[i]]==tip[x][y] && best[x+dx[i]][y+dy[i]]>best[x][y])
                            {

                                best[x+dx[i]][y+dy[i]]=best[x][y];
                                if(viz[x+dx[i]][y+dy[i]]);
                                else
                                {
                                viz[x+dx[i]][y+dy[i]]=1;
                                q[(++dr)%mod].x=x+dx[i];
                                q[dr%mod].y=y+dy[i];
                                }
                            }
                }
		}
   /* for(i=1;i<=n;++i)
        {
            for(j=1;j<=m;++j)
                printf("%d ",best[i][j]);
            printf("\n");
        }*/
    printf("%d\n",best[cl][cc]);
    return 0;
}