Cod sursa(job #1646370)

Utilizator rares00Foica Rares rares00 Data 10 martie 2016 15:57:35
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.8 kb
#include <iostream>
#include <fstream>
#define INF 25000
using namespace std;
ifstream in("castel.in");
ofstream out("castel.out");
int n,p,k,nr,nrMax=1;
int a[151][151],b[151][151];
bool chei[22501],ok;
int x0,y0,inc,sf;
struct coada{
    int x;
    int y;
}c[22501];

void citeste()
{
    int nr=0;
    in>>n>>p>>k;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=p;++j)
            b[i][j]=++nr;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=p;++j)
            in>>a[i][j];
}
bool interior(int x,int y)
{
    if(x>=1 && x<=n && y>=1 && y<=p)
        return 1;
    return 0;
}
void LEE(int x0,int y0)
{
    //formeaza mat
    int m[151][151],i,j;
    for(i=1;i<=n;++i)
        for(j=1;j<=p;++j)
            m[i][j]=INF;
    m[x0][y0]=1;

    inc=sf=1;
    c[sf].x=x0;
    c[sf].y=y0;
    nr=1;

    while(sf>=inc)//cat timp coada nu e vida
    {
        x0=c[inc].x;
        y0=c[inc].y;
        ++inc;

        if(interior(x0+1,y0) && m[x0+1][y0]>m[x0][y0]+1 && chei[a[x0+1][y0]])
        {
            m[x0+1][y0]=m[x0][y0]+1;
            //if(m[x0+1][y0]>nrMax)
            //    nrMax=m[x0+1][y0];
            ++nr;

            ++sf;
            c[sf].x=x0+1;
            c[sf].y=y0;

            if(chei[b[x0+1][y0]]==0)
                ok=1;
            chei[b[x0+1][y0]]=1;
        }
        if(interior(x0,y0+1) && m[x0][y0+1]>m[x0][y0]+1 && chei[a[x0][y0+1]])
        {
            m[x0][y0+1]=m[x0][y0]+1;
            //if(m[x0][y0+1]>nrMax)
            //    nrMax=m[x0][y0+1];
            ++nr;

            ++sf;
            c[sf].x=x0;
            c[sf].y=y0+1;

            if(chei[b[x0][y0+1]]==0)
                ok=1;
            chei[b[x0][y0+1]]=1;
        }
        if(interior(x0-1,y0) && m[x0-1][y0]>m[x0][y0]+1 && chei[a[x0-1][y0]])
        {
            m[x0-1][y0]=m[x0][y0]+1;
            //if(m[x0-1][y0]>nrMax)
            //    nrMax=m[x0-1][y0];
            ++nr;

            ++sf;
            c[sf].x=x0-1;
            c[sf].y=y0;

            if(chei[b[x0-1][y0]]==0)
                ok=1;
            chei[b[x0-1][y0]]=1;
        }
        if(interior(x0,y0-1) && m[x0][y0-1]>m[x0][y0]+1 && chei[a[x0][y0-1]])
        {
            m[x0][y0-1]=m[x0][y0]+1;
            //if(m[x0][y0-1]>nrMax)
            //    nrMax=m[x0][y0-1];
            ++nr;

            ++sf;
            c[sf].x=x0;
            c[sf].y=y0-1;

            if(chei[b[x0][y0-1]]==0)
                ok=1;
            chei[b[x0][y0-1]]=1;
        }
    }
}
int main()
{
    citeste();

    x0=k/p+1;
    if(k%p==0)
        y0=p;
    else
        y0=k%p;
    chei[a[x0][y0]]=1;

    do{
        ok=0;
        LEE(x0,y0);
        if(nrMax<nr)
            nrMax=nr;
    }while(ok==1);

    out<<nrMax;
    return 0;
}