Cod sursa(job #717396)

Utilizator SpiriFlaviuBerbecariu Flaviu SpiriFlaviu Data 19 martie 2012 21:39:06
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.46 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];

bool vizitat[152][152];

vector<int> cheie;
int main()
{
    int gata=0,x,i,j,nrcam,a[151][151],in,k;
    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;
    while(!gata)
    {
        gata=1;
        for(in=1;in<=nrcam;in++)
        {
            i=camera[in].x;
            j=camera[in].y;
            for(k=0;k<4;k++)
                if(inside(i+di[k],j+dj[k])
                   && !vizitat[i+di[k]][j+dj[k]]
                   && 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;

                }
        }



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