Cod sursa(job #1410304)

Utilizator popescu.octavianPopescu Octavian popescu.octavian Data 30 martie 2015 23:22:45
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.6 kb
#include <fstream>
#include <queue>
#include <vector>
#define pb push_back
#define NMax 151

using namespace std;

ifstream f("castel.in");
ofstream g("castel.out");

queue <int> Q;
vector <int> list[NMax*NMax+1];

int a[NMax][NMax], m, n, i, j, i1, j1, i2 ,j2, x, y, xx, yy, k, sol;
bool viz[NMax][NMax], cheie[NMax*NMax];
short const dx[]={-1,0,1,0}, dy[]={0,1,0,-1};

int nrkey(int i, int j)
{
    return n*(i-1)+j;
}
int linie(int k)
{
    if(k%n==0) return k/n;
    return k/n+1;
}
int coloana(int k)
{
    if(k%n==0) return n;
    return k%n;
}
int inmatrice(int i, int j)
{
    if(i>0&&i<=m&&j>0&&j<=n)
        return 1;
    return 0;
}
int main()
{
    f>>m>>n>>k;
    for(i=1;i<=m;i++)
        for(j=1;j<=n;j++)
            f>>a[i][j];
    i1=linie(k); j1=coloana(k);
    viz[i1][j1]=1;
    Q.push(k);
    while(!Q.empty())
    {
        x=Q.front();
        sol++;
        cheie[x]=1;
        for(vector<int>::iterator it=list[x].begin(); it!=list[x].end(); it++)
        {
            if(!viz[linie(*it)][coloana(*it)])
            {
                Q.push(*it);
                viz[linie(*it)][coloana(*it)]=1;
            }
        }
        i2=linie(x); j2=coloana(x);
        for(i=0;i<4;i++)
        {
            xx=i2+dx[i]; yy=j2+dy[i];
            if(!inmatrice(xx,yy)||viz[xx][yy]) continue;
            if(cheie[a[xx][yy]])
            {
                Q.push(nrkey(xx,yy));
                viz[xx][yy]=1;
            }
            else list[a[xx][yy]].pb(nrkey(xx,yy));
        }
        Q.pop();
    }
    g<<sol<<'\n';
    return 0;
}