Cod sursa(job #1104767)

Utilizator pop_bogdanBogdan Pop pop_bogdan Data 10 februarie 2014 23:43:44
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.64 kb
#include <fstream>
#include <queue>
#include <cstring>
using namespace std;
using std::swap;

ifstream is("castel.in");
ofstream os("castel.out");

#define Inside iv >= 1 && jv >= 1 && iv <= m && jv <= n

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

int m,n,k,Solution;
int o(0);
int x[155][155];
queue <pair<int,int> > Q;
queue <pair<int,int> > Qaux;
bool Key[22501];
bool marked[155][155];


void Input();
void BF();

int main()
{
    Input();
    BF();
    return 0;
}

void Input()
{
    is >> m >> n >> k;
    for ( int i = 1; i <= m; ++i )
        for ( int j = 1; j <= n; ++j )
            is >> x[i][j];
    Key[k] = true;
    if (k % n == 0)
        Q.push(make_pair(k/n+1,n));
    else
        Q.push(make_pair(k/n+1,k%n));
}

void BF()
{
    int i,j,iv,jv;
    int aux;
    bool Stou;
    marked[Q.front().first][Q.front().second] = true;
    while ( 1 != 0)
    {
    swap(Qaux,Q);
    Stou = false;
    while ( !Qaux.empty() )
    {
        i = Qaux.front().first;
        j = Qaux.front().second;
        Q.push(make_pair(i,j));
        Qaux.pop();
        for ( int d = 0; d < 4; ++d )
        {
            iv = i + di[d];
            jv = j + dj[d];
            aux = x[iv][jv];
            if ( Inside && Key[aux] == true && marked[iv][jv] == false )
            {
                marked[iv][jv] = true;
                Key[(iv-1)*n+jv] = true;
                Stou = true;
                Solution++;
                Qaux.push(make_pair(iv,jv));
            }
        }
    }
    if ( Stou == false )
    {
        os << Solution;
        return;
    }
    }
}