Cod sursa(job #1181251)

Utilizator andreiiiiPopa Andrei andreiiii Data 2 mai 2014 12:19:02
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.85 kb
#include <algorithm>
#include <bitset>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int Nmax=155;
const int dx[]={-1, 0, 1, 0}, dy[]={0, 1, 0, -1};

int N, M, K;
bitset <Nmax*Nmax> Av, V, Ac;
vector <int> A[Nmax*Nmax], G[Nmax*Nmax];
queue <int> Q;

int Sol;

int getkey(int x, int y)
{
    return (x-1)*M+y;
}

/*pair<int, int> getcoord(int key)
{
    int x, y;
    y=(key-1)%M+1;
    x=(key-y)/M+1;

    return make_pair(x, y);
}*/

void build_graph()
{
    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            int x, y;
            for(int k=0;k<4;k++)
            {
                x=i+dx[k];
                y=j+dy[k];
                if(x<1||x>N||y<1||y>M) continue;

                G[getkey(i, j)].push_back(getkey(x, y));
            }
        }
    }

    N*=M;
}

void Bfs(int node)
{
    Av[node]=1;
    V[node]=1;
    Ac[node]=1;

    for(Q.push(node);!Q.empty();Q.pop())
    {
        node=Q.front();
        Sol++;

        for(auto p: A[node])
        {
            Av[p]=1;
            if(Ac[p]&&!V[p])
            {
                V[p]=1;
                Q.push(p);
            }
        }

        for(auto p: G[node])
        {
            if(V[p]) continue;

            Ac[p]=1;
            if(Av[p])
            {
                V[p]=1;
                Q.push(p);
            }
        }
    }
}

void Dfs(const int node)
{

}

int main()
{
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);

    scanf("%d%d%d", &N, &M, &K);

    for(int i=1;i<=N;i++)
    {
        for(int j=1;j<=M;j++)
        {
            int x;
            scanf("%d", &x);

            A[x].push_back(getkey(i, j));
        }
    }

    build_graph();

    Bfs(K);

    printf("%d\n", Sol);
}