Cod sursa(job #1641586)

Utilizator ShayTeodor Matei Shay Data 9 martie 2016 07:56:25
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.69 kb
#include <iostream>
#include <fstream>
#include <queue>

using namespace std;

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

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

queue < pair < int, int > > coada;

int castel[150][150];
int camDeschise[150][150];
int n,m,k,istart,jstart,nrchei,directie,r, chei[200];

void CoordCamera(int k){
    int i,j,rest;
    rest=k%m;
    if (rest==0){
        i=k/m;
        j=m;
    }
    if (rest>0){
        i=k/m+1;
        j=rest;
    }
    istart=i;
    jstart=j;
}

int Verificare(int i, int j){ // modul de generare a unei chei pentru celula i-j
    return (i-1)*n+j;
}

bool OK(int i, int j, int q){ // verifica daca celula i-j indeplineste conditiile de continuare
    if (i<1 || j<1 || i>m || j>n)
        return 0;
    for (r=1;r<=q;r++)
        if (chei[r]==castel[i][j])
        {
            return 1;
        }
    return 0;
}

bool continua(int i, int j, int q){ // se verifica daca celula i-j ce genereaza o cheie se regaseste deja in vecorul cheii
   for (r=1;r<=q;r++)
        if (chei[r]==Verificare(i,j))
        {
            return 0;
        }
    return 1;
}

void cit(){
    fin>>m>>n>>k;
    for (int i=1;i<=m;i++)
        for (int j=1;j<=n;j++)
            fin>>castel[i][j];
}

void lee(){
    int i,j,iu,ju;
    camDeschise[istart][jstart]=1;
    nrchei=1; // nr de chei de acces
    chei[nrchei]=k; // vectorul in care se retin cheile de acces
    coada.push(make_pair(istart,jstart));
    while (!coada.empty())
    {

        i=coada.front().first;
        j=coada.front().second;
        coada.pop();
        for (directie=0;directie<4;directie++)
        {
            iu=i+di[directie];
            ju=j+dj[directie];
            if (OK(iu,ju,nrchei))
            {
                if (continua(iu,ju,nrchei) && camDeschise[iu][ju]<1) // pentru prima parcurgere unde se genereaza o noua cheie
                {
                    camDeschise[iu][ju]=camDeschise[i][j]+1;
                    nrchei++;
                    chei[nrchei]=Verificare(iu,ju);
                    coada.push(make_pair(iu,ju));
                }
                else
                     // <=4 deoarece se poate patrunde intr-o celula din maxim 4 directii.
                     if (camDeschise[iu][ju]<=4) // numai pentru celulele prin care s-a mai trecut cel putin o data si deja s-a generat o cheie
                        {
                            camDeschise[iu][ju]=camDeschise[i][j]+1;
                            coada.push(make_pair(iu,ju));
                        }
            }

        }
    }

}

int main()
{
    cit();
    CoordCamera(k);
    lee();
    fout<<nrchei;
}