Cod sursa(job #328416)

Utilizator DraStiKDragos Oprica DraStiK Data 1 iulie 2009 22:39:48
Problema Barbar Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <stdio.h>
#define DIM 1005

int dx[4]={1,0,-1, 0};
int dy[4]={0,1, 0,-1};
struct queue {int x,y;} q[DIM*DIM];
int a[DIM][DIM],b[DIM][DIM];
int n,m,sol,xi,yi,xf,yf,in,sf;

void read ()
{
    char ch;
    int i,j;
    scanf ("%d%d\n",&n,&m);
    for (i=1; i<=n; ++i)
        for (j=1; j<=m+1; ++j)
        {
            scanf ("%c",&ch);
            if (ch=='*')
                a[i][j]=-1;
            else if (ch=='D')
            {
                q[++sf].x=i;
                q[sf].y=j;
                a[i][j]=1;
            }
            else if (ch=='I')
            {
                xi=i;
                yi=j;
            }
            else if (ch=='O')
            {
                xf=i;
                yf=j;
            }
        }
}

void bord ()
{
    int i;
    for (i=0; i<=n+1; ++i)
        a[i][0]=a[i][m+1]=b[i][0]=b[i][m+1]=-1;
    for (i=0; i<=m+1; ++i)
        a[0][i]=a[n+1][i]=b[0][i]=b[n+1][i]=-1;
}

void bf ()
{
    int i;
    for (in=1; in<=sf; ++in)
        for (i=0; i<4; ++i)
            if(!a[q[in].x+dx[i]][q[in].y+dy[i]])
            {
                a[q[in].x+dx[i]][q[in].y+dy[i]]=a[q[in].x][q[in].y]+1;
                q[++sf].x=q[in].x+dx[i];
                q[sf].y=q[in].y+dy[i];
            }
}

void clean ()
{
    int i,j;
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j)
		 {
            b[i][j]=0;
			 if (a[i][j]==1 || a[i][j]==-1)
				 b[i][j]=-1;
		 }
}

int test (int val)
{
    int i;
    b[xi][yi]=1;
    for (q[in=sf=1].x=xi, q[1].y=yi; in<=sf; ++in)
	 {
		 if (a[q[in].x][q[in].y]<val)
			 return 0;
        for (i=0; i<4; ++i)
            if (!b[q[in].x+dx[i]][q[in].y+dy[i]] && a[q[in].x+dx[i]][q[in].y+dy[i]]>=val)
            {
                b[q[in].x+dx[i]][q[in].y+dy[i]]=b[q[in].x][q[in].y]+1;
                q[++sf].x=q[in].x+dx[i];
                q[sf].y=q[in].y+dy[i];
            }
	 }
    return b[xf][yf];
}

void solve ()
{
    int st,dr,mij;
    for (sol=-1, st=2, dr=n*m+1; st<=dr; )
    {
        mij=(st+dr)/2;
        clean ();
        if (test (mij))
        {
            sol=mij;
            st=mij+1;
        }
        else
            dr=mij-1;
    }
    printf ("%d",sol-1);
}

int main ()
{
    freopen ("barbar.in","r",stdin);
    freopen ("barbar.out","w",stdout);
    read ();
    bord ();
    bf ();
    solve ();
    return 0;
}