Cod sursa(job #1789958)

Utilizator nnnmmmcioltan alex nnnmmm Data 27 octombrie 2016 17:28:49
Problema BMatrix Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define MaxN 205
#define INF 2147483647

FILE *IN,*OUT;
int N,M,L[MaxN][MaxN],C[MaxN][MaxN],RL[MaxN][MaxN],RC[MaxN][MaxN];
struct ___Cancer___{int x,y;}Fwd[MaxN][MaxN],Bkd[MaxN][MaxN];
bool v[MaxN][MaxN];
char Ch;
int main()
{
    IN=fopen("bmatrix.in","r");
    OUT=fopen("bmatrix.out","w");

    fscanf(IN,"%d%d ",&N,&M);
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            fscanf(IN,"%c ",&Ch);
            v[i][j]=Ch-'0';
        }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            if(v[i][j])
                L[i][j]=C[i][j]=0;
            else
            {
                L[i][j]=L[i][j-1]+1;
                C[i][j]=C[i-1][j]+1;
            }
        }
    for(int i=N;i>=1;i--)
        for(int j=M;j>=1;j--)
        {
            if(v[i][j])
                RL[i][j]=RC[i][j]=0;
            else
            {
                RL[i][j]=RL[i][j+1]+1;
                RC[i][j]=RC[i+1][j]+1;
            }
        }
    for(int i=1;i<=N;i++)
        for(int j=1;j<=M;j++)
        {
            if(v[i][j])
            {
                Fwd[i][j].x=i,Fwd[i][j].y=j;
            }
            else
            {
                int Max=INF;
                for(int k=j;k-C[i][j]+1;k--)
                {
                    Max=std::min(Max,L[i][j]);
                }
                Fwd[i][j].x=i-C[i][j]+1;
                Fwd[i][j].y=j-Max+1;
                if((i-1-Fwd[i-1][j].x+1)*(j-Fwd[i-1][j].y+1)>(i-Fwd[i][j].x+1)*(j-Fwd[i][j].y+1))
                    Fwd[i][j]=Fwd[i-1][j];
                if((i-Fwd[i][j-1].x+1)*(j-1-Fwd[i][j-1].y+1)>(i-Fwd[i][j].x+1)*(j-Fwd[i][j].y+1))
                    Fwd[i][j]=Fwd[i][j-1];
            }
        }

    for(int i=N;i>0;i--)
        for(int j=M;j>0;j--)
        {
            if(v[i][j])
            {
                Bkd[i][j].x=i,Bkd[i][j].y=j;
            }
            else
            {
                int Max=INF;
                for(int k=j;k+RC[i][j]-1;k++)
                {
                    Max=std::min(Max,RL[i][j]);
                }
                Bkd[i][j].x=i+C[i][j]-1;
                Bkd[i][j].y=j+Max-1;
                if((Bkd[i+1][j].x-i)*(Bkd[i+1][j].y-j+1)>(Bkd[i][j].x-i+1)*(Bkd[i][j].y-j+1))
                    Bkd[i][j]=Bkd[i+1][j];
                if((Bkd[i][j+1].x-i+1)*(Bkd[i][j-1].y-j)>(Bkd[i][j].x-i+1)*(Bkd[i][j].y-j+1))
                    Bkd[i][j]=Bkd[i][j+1];
            }
        }
    return 0;
}