Cod sursa(job #1105301)

Utilizator japjappedulapPotra Vlad japjappedulap Data 11 februarie 2014 18:13:17
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

#define TX pair <int,int>
#define f first
#define s second

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

const int di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};

int n, m, p;
bool b[155][155];
bool key[155*155];
TX F, o;

queue <TX> Q;
queue <int> Qs;
vector < vector<int> > v;
vector <int> vs;

void Read();
void Lee();
void Solve();
bool Ok(int i, int j);
TX Room(int x);

int main()
{
    Read();
    Solve();
    //Lee();
    is.close();
    os.close();
    return 0;
}

void Solve()
{
    int x;
    Qs.push(p);
    while (!Qs.empty())
    {
        x = Qs.front(); Qs.pop();
        for (int i = 0; i < v[x].size(); ++i)
        {
            Qs.push(v[x][i]);
            if (key[v[x][i]] == 0) key[v[x][i]] = 1, vs.push_back(v[x][i]);
        }
        v[x].clear();
    }
    for (int i = 0; i < vs.size(); ++i)
    {
        F = Room(vs[i]);
        b[F.f][F.s] = 1;
    }
    os << vs.size() << '\n';
    /*for (int i = 0; i <= n+1; ++i)
    {
        for (int j = 0; j <= m+1; ++j)
            os << b[i][j] << ' ';
        os << '\n';
    }*/
};

void Lee()
{
    int i, j, iv, jv, cnt = 0;
    Q.push(Room(p));
    while (!Q.empty())
    {
        i = Q.front().f, j = Q.front().s; Q.pop();
        cnt++;
        for (int dir = 0; dir < 4; dir++)
        {
            iv = i + di[dir];
            jv = j + dj[dir];
            if (Ok(iv, jv) && b[iv][jv] == 1)
            {
                b[iv][jv] = 0;
                Q.push(make_pair(iv, jv));
            }
        }
    }
    //os << cnt;
};

void Read()
{
    is >> n >> m >> p;
    int x;
    v.resize(n*m+1);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
        {
            is >> x;
            v[x].push_back((i-1)*m + j);
        }
};

bool Ok(int i, int j)
{
    if (i < 1 || i > n || j < 1 || j > m) return false;
    return true;
};

TX Room(int x)
{
    o.f = x/m;
    ++o.f;
    o.s = x % m;
    if (o.s == 0) o.s = m, o.f--;
    return o;
};