Cod sursa(job #609518)

Utilizator mihai995mihai995 mihai995 Data 21 august 2011 20:52:34
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include <fstream>
#include <vector>
using namespace std;

const int N=22501;
int v[N],stack[N],vecin[5],n,m,nr;
bool use[4*N],acc[N];
vector<int> need[N];

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

inline void push(int x)
{
    stack[++stack[0]]=x;
}

inline void pop(int& x)
{
    x=stack[stack[0]--];
}

inline void det(int x)
{
    vecin[0]=0;
    if (x>m)
        vecin[++vecin[0]]=x-m;
    if (x<=(n-1)*m)
        vecin[++vecin[0]]=x+m;
    if (x%m)
        vecin[++vecin[0]]=x+1;
    if (x%m!=1)
        vecin[++vecin[0]]=x-1;
}

void bfs(int x)
{
    push(x);
    while (stack[0])
    {
        pop(x);
        if (use[x])
            continue;
        use[x]=true;
        nr++;
        for (vector<int>::iterator i=need[x].begin();i!=need[x].end();i++)
            if (!use[*i] && acc[*i])
                push(*i);
        det(x);
        for (int i=1;i<=vecin[0];i++)
        {
            acc[vecin[i]]=true;
            if (!use[vecin[i]] && use[v[vecin[i]]])
                push(vecin[i]);
        }
    }
}

int main()
{
    int S;
    in>>n>>m>>S;
    for (int i=1;i<=n*m;i++)
    {
        in>>v[i];
        need[v[i]].push_back(i);
    }
    bfs(S);
    out<<nr<<"\n";
}