Cod sursa(job #2357164)

Utilizator tgm000Tudor Mocioi tgm000 Data 27 februarie 2019 10:25:02
Problema Barbar Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<cstdio>
#include<cstring>
char a[1002][1002];
char aux[1002];
int dmin[1002][1002];
char c[1002][1002];
struct pos{int x,y;};
pos q[1000001];
int dx[]={-1,0,1,0};
int dy[]={0,1,0,-1};
pos crt,ext,in,out;
int limd;
void fillt(int i,int j){
    c[i][j]=1;
    for(int k=0;k<=3;k++)
        if(c[i+dx[k]][j+dy[k]]==0&&dmin[i+dx[k]][j+dy[k]]>=limd)
            fillt(i+dx[k],j+dy[k]);
}
int main(){
    int n,m,i,j,ic,sf,k,st,dr,poz;
    freopen("barbar.in","r",stdin);
    freopen("barbar.out","w",stdout);
    scanf("%d%d\n",&n,&m);
    for(i=1;i<=n;i++){
        scanf("%s",a[i]);
        strcpy(aux,a[i]);
        strcpy(a[i]+1,aux);
        for(j=1;j<=m;j++)
            dmin[i][j]=2e9;
    }
    for(i=0;i<=n+1;i++){
        a[i][0]=a[i][m+1]='*';
        c[i][0]=c[i][m+1]=-1;
    }
    for(j=0;j<=m+1;j++){
        a[0][j]=a[n+1][j]='*';
        c[0][j]=c[n+1][j]=-1;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++){
            if(a[i][j]=='D'){
                dmin[i][j]=1;
                ic=sf=1;
                q[1].x=i;q[1].y=j;
                while(ic<=sf){
                    crt=q[ic];
                    for(k=0;k<=3;k++){
                        ext.x=crt.x+dx[k];
                        ext.y=crt.y+dy[k];
                        if(a[ext.x][ext.y]!='*'&&dmin[crt.x][crt.y]+1<dmin[ext.x][ext.y]){
                            sf++;
                            q[sf]=ext;
                            dmin[ext.x][ext.y]=dmin[crt.x][crt.y]+1;
                        }
                    }
                    ic++;
                }
            }
            if(a[i][j]=='I'){
                in.x=i;
                in.y=j;
            }
            if(a[i][j]=='O'){
                out.x=i;
                out.y=j;
            }
        }
    dr=0;
    for(i=0;i<=n+1;i++)
        for(j=0;j<=m+1;j++){
            if(dmin[i][j]==2e9)
                dmin[i][j]=0;
            if(dmin[i][j]>dr)
                dr=dmin[i][j];
        }
    st=1;
    while(st<=dr){
        limd=(st+dr)/2;
        fillt(in.x,in.y);
        if(c[out.x][out.y]==1){
            st=limd+1;
            poz=limd;
        }else
            dr=limd-1;
        for(i=1;i<=n;i++)
            for(j=1;j<=m;j++)
                c[i][j]=0;
    }
    printf("%d",poz-1);
    return 0;
}