Cod sursa(job #1730538)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 17 iulie 2016 01:55:41
Problema Castel Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.75 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];
queue <pair <int, int>> q;
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;

void bfs()
{
    while(!q.empty())
    {
        pair <int, int> p = q.front();
        q.pop();
        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]])
            {
                if( gasit[(x - 1) * m + y] == 0 )
                    ok = true;

                gasit[(x - 1) * m + y] = 1;
                q.push(make_pair(x, y));
                descuiat[x][y] = 1;

                if( marcat[x][y] == 0 ) {
                    marcat[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;
    marcat[x][y] = 1;
    while(ok == true)
    {
        for( int i = 1; i <= n; i ++ )
            for( int j = 1; j <= m; j ++ )
                descuiat[i][j] = 0;
        descuiat[x][y] = 1;
        q.push(make_pair(x, y));
        ok = false;
        bfs();
    }
    out << ans;
    return 0;
}