Cod sursa(job #1119178)

Utilizator TudorMTudor Moldovanu TudorM Data 24 februarie 2014 15:56:32
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include<fstream>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
int a[171][171], nr, b[171][171],maxi,dx[]={-1,0,1,0},m,n,k, dy[]={0,1,0,-1},fr[30000],l1,col1, numar,v[20000];
struct{int x, y;}c[30000],lista[20000],origine[20000];
struct{int nord,est,sud,vest;}patrat[170][170];
int interior(int x, int y)
{
    if(x>=1&&x<=m&&y>=1&&y<=n)return 1;
    return 0;
}
void citire()
{
    int i, j;
    f>>m>>n>>k;
    for(i=1;i<=m;i++)
    {
        for(j=1;j<=n;j++)
        {
            f>>a[i][j];
            b[i][j]=++nr;
            if(nr==k)
            {
                l1=i;
                col1=j;
            }
        }
    }
}
int posibil(int x, int y, int xv, int yv, int i)
{
    if(i==0&&patrat[x][y].nord==1)return 0;
    if(i==1&&patrat[x][y].est==1)return 0;
    if(i==2&&patrat[x][y].sud==1)return 0;
    if(i==3&&patrat[x][y].vest==1)return 0;
    return 1;
}
void lee(int x, int y)
{
    int i, j,l, xv, yv, p, u;
    p=u=1;
    fr[b[x][y]]=1;
    c[u].x=x;
    c[u].y=y;
    while(p<=u)
    {
        x=c[p].x;
        y=c[p++].y;
        for(i=0;i<=3;i++)
        {
            xv=x+dx[i];
            yv=y+dy[i];
            if(interior(xv,yv)&&fr[a[xv][yv]]&&posibil(x,y,xv,yv,i))
            {
                fr[b[xv][yv]]=1;
                c[++u].x=xv;
                c[u].y=yv;
                if(i==0)
                {
                    patrat[x][y].nord=1;
                    patrat[xv][yv].sud=1;
                }
                else if(i==1)
                {
                    patrat[x][y].est=1;
                    patrat[xv][yv].vest=1;
                }
                else if(i==2)
                {
                    patrat[x][y].sud=1;
                    patrat[xv][yv].nord=1;
                }
                else
                { patrat[x][y].vest=1;
                patrat[xv][yv].est=1;
                }
                for(j=1;j<=numar;j++)
                {
                    if(fr[a[lista[j].x][lista[j].y]]&&posibil(origine[i].x,origine[i].y,lista[i].x,lista[i].y,i));
                    {
                        c[++u].x=lista[j].x;
                        c[u].y=lista[j].y;
                        for(l=j;l<=numar;l++)lista[l]=lista[l+1];
                        numar--;
                        j--;
                    }
                }
            }
            else if(interior(xv,yv)&&posibil(x,y,xv,yv,i))
            {
                lista[++numar].x=xv;
                lista[numar].y=yv;
                origine[numar].x=x;//retine vecinul
                origine[numar].y=y;//retine vecinul
                v[numar]=i;//retine directia
            }
        }
    }
}
int main()
{
    citire();
    lee(l1,col1);
    int i;
    for(i=1;i<=nr;i++)if(fr[i])maxi++;
    g<<maxi;
    f.close();
    g.close();
    return 0;
}