Cod sursa(job #1730545)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 17 iulie 2016 02:12:24
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.44 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <queue>
using namespace std;
ifstream in("castel.in");
ofstream out("castel.out");
const int maxn = 155;
bitset <maxn> descuiat[maxn], marcat[maxn];
pair <int, int> q[maxn];
int M[maxn][maxn];
int gasit[maxn * maxn];
int n, m;

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

inline bool inside(int x, int y)
{
    if(x >= 1 && y >= 1 && x <= n && y <= m)
        return 1;
    return 0;
}

bool ok = 1;
int ans = 1;
int dr = 1;
int st = 1;

void bfs()
{
    for(int j = st; j <= dr; j++)
    {
        pair <int, int> p = q[j];
        for(int i = 0; i < 4; i++)
        {
            int x = p.first + dx[i];
            int y = p.second + dy[i];
            if(inside(x, y) && !descuiat[x][y] && gasit[M[x][y]])
            {
                ok = true;
                gasit[(x - 1) * m + y] = 1;
                q[++dr] = make_pair(x, y);
                descuiat[x][y] = 1;
                ans ++;
            }
        }
    }
}

int main()
{
    int k;
    in >> n >> m >> k;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++)
            in >> M[i][j];
    int x = (k - 1) / m + 1;
    int y = (k - 1) % m + 1;
    gasit[k] = 1;
    descuiat[x][y] = 1;

    st = dr = 1; q[st] = make_pair(x, y);
    while(ok == true)
    {
        ok = false;
        bfs();
    }
    out << ans;
    return 0;
}