Cod sursa(job #864307)

Utilizator narcis_vsGemene Narcis - Gabriel narcis_vs Data 24 ianuarie 2013 20:55:28
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<cstdio>
#include<iostream>
#include<stack>
#include<vector>
#define In "castel.in"
#define Out "castel.out"
#define N 155
using namespace std;
struct Coord{int lin,col;};
struct T
{
    bool am;
    vector<int>v;
};
T b[N*N];
int n, m, ci;
int sol;
int a[N][N];
int uz[N][N];
stack<Coord>St;

inline int ToCamera (int x, int y);
inline void ToCoord(int cam,int &x,int &y);
void Rezolvare();

void Citire()
{
    int i,j;
    freopen(In,"r",stdin);
    freopen(Out,"w",stdout);
    scanf("%d %d %d", &n, &m, &ci);
    for(i = 1; i <= n; i++)
        for(j = 1;j <=m; j++)
            scanf("%d", &a[i][j]);
}

int main()
{
    Citire();
    Rezolvare();
    printf("%d\n",sol);
    return 0;
}
void Actualizare(int c)
{
    int i,k,n;Coord vec;
    n = b[c].v.size();
    if(n)
    {
        for(i=0;i<n;i++)
        {
            k = b[c].v[i];
            ToCoord(k,vec.lin,vec.col);
            b[k].am = 1;
            uz[vec.lin][vec.col] = 1;
            St.push(vec);
        }
        b[c].v.clear();
    }
}
void Rezolvare()
{
    int dl[]={1, 0,-1, 0};
    int dc[]={0, 1, 0,-1};
    int c,i,k;
    Coord p,vec;

    ToCoord(ci,p.lin,p.col);
    uz[p.lin][p.col] = 1 ;
    b[ci].am = 1;
    St.push(p);
    while(!St.empty())
    {
        p = St.top();
        St.pop();
        sol++;
        c = ToCamera(p.lin,p.col);
        Actualizare(c);
        for(i = 0 ; i < 4 ; i++)
        {
            vec.lin = p.lin + dl [i];
            vec.col = p.col + dc [i];
            k = a[vec.lin][vec.col];
            if(uz[vec.lin][vec.col]==0 && b[k].am==1)
            {
                uz[vec.lin][vec.col] = 1;
                c = ToCamera(vec.lin,vec.col);
                b[c].am = 1;
                St.push(vec);
                Actualizare(c);
            }
            else
            {
                if(uz[vec.lin][vec.col]==0 && b[k].am==0)
                {
                    c = ToCamera(vec.lin,vec.col);
                    b[k].v.push_back(c);
                    uz[vec.lin][vec.col] = 1;
                }
            }
        }
    }
}

inline void ToCoord(int cam,int &x,int &y)
{
    y = cam % m;
    if(y==0)
        y = m;
    cam -= y;
    x = cam / m +1;
}

inline int ToCamera (int x, int y)
{
    return m*(x-1) + y;
}