Cod sursa(job #1412358)

Utilizator Liviu98Dinca Liviu Liviu98 Data 1 aprilie 2015 11:43:49
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.66 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#define NMax 155
using namespace std;
int Dx[4]={-1,0,1,0};
int Dy[4]={0,1,0,-1};
int N,M,K,z,ok,nr,cd;
int d[NMax*NMax];
int A[NMax][NMax],B[NMax][NMax];
struct Punct
{
    int x,y;
}start,p,v;

void Citire()
{
    ifstream g("castel.in");
    g>>N>>M>>K;
    for(int i=1;i<=N;i++)
    for(int j=1;j<=M;j++)
    {
        nr++;
        g>>A[i][j];
        B[i][j]=nr;
        if(K==nr)
        {
            start.x=i;
            start.y=j;
        }
    }
}

void Afisare()
{
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
            cout<<A[i][j]<<' ';
        cout<<endl;
    }
}

inline bool Posibil(int x,int y)
{
    if(x>=1 && y>=1 && x<=N && y<=M)
        return true;
    return false;
}

void BFS()
{
    d[B[start.x][start.y]]=1;
    ok=1,nr=0,cd=1;
    A[start.x][start.y]=-1;
    int Q[NMax*NMax][2];
    Q[0][0]=start.x;
    Q[0][1]=start.y;
    while(ok==1)
    {
        ok=0;
        for(int i=0;i<=nr;i++)
        {
            for(int d1=0;d1<4;d1++)
            {
                v.x=Q[i][0]+Dx[d1];
                v.y=Q[i][1]+Dy[d1];
                if(A[v.x][v.y]!=-1)
                if(d[A[v.x][v.y]]==1)
                {
                    nr++;
                    Q[nr][0]=v.x;
                    Q[nr][1]=v.y;
                    A[v.x][v.y]=-1;
                    d[B[v.x][v.y]]=1;
                    cd++;
                    ok=1;
                }
            }
        }
    }
}

int main()
{
    Citire();
    BFS();
    ofstream f("castel.out");
    f<<cd;
    //Afisare();
}