Cod sursa(job #2456357)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 14 septembrie 2019 11:13:18
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream fin("castel.in");
ofstream fout("castel.out");
 
int n, m, k, a[155][155], dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, contor;
vector <pair <int, int> > cheie[155 * 155];
bool viz[155][155], fr[155 * 155], bagat[155][155];
queue <pair <int, int> > coada;
 
int GetRow(int x)
{
    int row = x / m;
    if (x % m != 0)
        ++row;
    return row;
}
 
int GetCol(int x)
{
    int row = GetRow(x);
    --row;
    row = 1 + m * row;
    int col = x - row + 1;
    return col;
}
 
int GetKey(int x, int y)
{
    return 1 + m * (x - 1) + y - 1;
}
 
bool Valid(int x, int y)
{
    return x >= 1 && x <= n && y >= 1 && y <= m && viz[x][y] == false;
}
 
int main()
{
    fin >> n >> m >> k;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            fin >> a[i][j];
        }
    }
    coada.push({GetRow(k), GetCol(k)});
    while (coada.size() > 0)
    {
        int x = coada.front().first;
        int y = coada.front().second;
        int key = GetKey(x, y);
        coada.pop();
        while (cheie[key].size() > 0)
        {
            int xx = cheie[key][cheie[key].size() - 1].first;
            int yy = cheie[key][cheie[key].size() - 1].second;
            if (viz[xx][yy] == false)
                coada.push({xx, yy}), viz[xx][yy] = true;
            cheie[key].pop_back();
        }
        viz[x][y] = true;
        fr[key] = 1;
        fr[a[x][y]] = 1;
        for (int w = 0; w < 4; ++w)
        {
            int xx = x + dx[w];
            int yy = y + dy[w];
            if (xx >= 1 && xx <= n && yy >= 1 && yy <= m && viz[xx][yy] == false)
            {
                if (fr[a[xx][yy]] == 1)
                {
                    coada.push({xx, yy});
                }
                else
                {
                    if (bagat[xx][yy] == false)
                    	cheie[a[xx][yy]].push_back({xx, yy}), bagat[xx][yy] = true;
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
        {
            contor = contor + viz[i][j];
        }
    }
    fout << contor << "\n";
    fin.close();
    fout.close();
    return 0;
}