Cod sursa(job #717512)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 19 martie 2012 22:57:29
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

ifstream fin("castel.in");
ofstream fout("castel.out");

const int di[]={1,-1,0,0};
const int dj[]={0,0,1,-1};


struct pozitie
{
    int x;
    int y;

};

int n, m;

bool inside(int i, int j)
{
    return i>=1 && j>=1 && i<=n && j<=m;
}

pozitie camera[62502],vecin[62502];

bool vizitat[152][152],vecin_here[152][152];

int nrcam,gata;

vector<int> cheie;

void update_vecin(pozitie v)
{
    if(binary_search(cheie.begin(),cheie.end(),(v.x-1)*m+v.y))
    {
        camera[++nrcam].x=v.x;
        camera[nrcam].y=v.y;
    }
    vecin_here[v.x][v.y]=false;
    gata=0;

}
int main()
{
    int x,i,j,a[151][151],in,k,nrvecin=0,inou,jnou,t;
    fin>>n>>m>>x;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            fin>>a[i][j];
    cheie.push_back(x);
    i=x/m+1;
    j=x%m;

    vizitat[i][j]=true;
    camera[1].x=i;
    camera[1].y=j;
    nrcam=1;
    t=1;
    while(!gata)
    {
        gata=2;
        for( ;t<=nrcam;t++)
        {
            for(k=0;k<4;k++)
            {
                inou=camera[t].x+di[k];
                jnou=camera[t].y+dj[k];
                if(inside(inou,jnou) && !vizitat[inou][jnou])
                {
                    if(binary_search(cheie.begin(),cheie.end(),a[inou][jnou]))
                    {
                        camera[++nrcam].x=inou;
                        camera[nrcam].y=jnou;
                        vizitat[inou][jnou]=true;
                        cheie.push_back((inou-1)*m+jnou);
                        sort(cheie.begin(),cheie.end());
                        gata=0;

                    }
                    else
                    {
                        vecin[++nrvecin].x=inou;
                        vecin[nrvecin].y=jnou;
                        vecin_here[inou][jnou]=true;

                    }
                }
            }
        }
        for(in=1;in<=nrvecin;in++)
        {
                inou=vecin[in].x;
                jnou=vecin[in].y;
                if(vecin_here[inou][jnou])
                    update_vecin(vecin[in]);
        }

    }
    fout<<nrcam;
    fin.close();
    fout.close();
    return 0;
}

 /*
        gata=1;
        for(in=1;in<=nrvecin;in++)
        {
            i=vecin[in].x;
            j=vecin[in].y;
            for(k=0;k<4;k++)
                if(inside(i+di[k],j+dj[k])
                   && !vizitat[i+di[k]][j+dj[k]])
                    if(binary_search(cheie.begin(),cheie.end(),a[i+di[k]][j+dj[k]]))
                    {
                        camera[++nrcam].x=i+di[k];
                        camera[nrcam].y=j+dj[k];
                        vizitat[i+di[k]][j+dj[k]]=true;
                        cheie.push_back((i+di[k]-1)*m+j+dj[k]);
                        sort(cheie.begin(),cheie.end());
                        gata=0;

                    }
                    else
                    {
                        vecin[++nrvecin].x=i+di[k];
                        vecin[++nrvecin].y=j+dj[k];

                    }
        }
*/