Cod sursa(job #1647388)

Utilizator ajeccAjechiloae Eugen ajecc Data 10 martie 2016 20:22:37
Problema Castel Scor 50
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.14 kb
#include <iostream>
#include <fstream>
#include <cmath>
#include <unordered_map>
#include <queue>
#include <utility>
#define for1(i,n) for(int i=1; i<=n; i++)
#define for0(i,n) for(int i=0; i<n; i++)
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
int n, m, k;
short cheie_necesara[151][151];
short cheie[151][151];
bool castel[151][151];
int startx, starty;
unordered_map<short, bool> am_cheia;
queue<pair<int,int> > coada;
void citire();
void fil(int x, int y);
void solve();

int main()
{
    citire();
    solve();

    return 0;
}

void citire()
{
    fin>>n>>m>>k;

    for1(i,n)
        for1(j,m)
            fin>>cheie_necesara[i][j];
    int c=1;
    for1(i,n)
        for1(j,m)
        {
            cheie[i][j]=c;
            if(c==k)
            {
                startx=i;
                starty=j;
            }
            c++;
        }
       // cout<<startx<<' '<<starty;
   /* for1(i,n)
    {
        for1(j,m)
            cout<<cheie[i][j]<<' ';
            cout<<endl;
    }*/


}

void fil(int x, int y)
{
    int dx[]={0,0,1,-1};
    int dy[]={1,-1,0,0};
    castel[x][y]=1;
    am_cheia[cheie[x][y]]=1;
  //  cout<<x<<' '<<y<<endl;
   // cout<<cheie[x][y]<< ' ';
    for0(i,4)
        if(x+dx[i]>0 && x+dx[i]<=n && y+dy[i]>0 && y+dy[i]<=m)
        {
            if(am_cheia[cheie_necesara[x+dx[i]][y+dy[i]]]==1 && castel[x+dx[i]][y+dy[i]]==0)
                fil(x+dx[i],y+dy[i]);
            else if(am_cheia[cheie_necesara[x+dx[i]][y+dy[i]]]==0)
                coada.push(make_pair(x+dx[i], y+dy[i]));
        }

              // cout<<x+dx[i]<<' '<<y+dy[i]<<endl;
}

void solve()
{
    fil(startx, starty);
    while(!coada.empty())
    {
        int x=coada.front().first;
        int y=coada.front().second;
        coada.pop();
       //cout<<am_cheia[cheie_necesara[1][3]]<<' ';
     //  cout<<castel[1][3];
        if(castel[x][y]==0 && am_cheia[cheie_necesara[x][y]])
            fil(x,y);
    }

    int sol=0;
    for1(i,n)
        for1(j,m)
            if(castel[i][j])
                sol++;
    fout<<sol;
}//