Cod sursa(job #2360594)

Utilizator aurelionutAurel Popa aurelionut Data 1 martie 2019 22:47:40
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.23 kb
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

const int NMAX = 155;
const int VMAX = 22505;
int n, m, k;
int a[NMAX][NMAX];
bool have[VMAX];
bool viz[NMAX][NMAX];
queue <int> q;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
vector <int> tried[VMAX];

inline int Convert1(int x, int y)
{
    return ((x - 1) * m + y);
}

inline pair <int, int> Convert2(int x)
{
    int i = (x - 1) / m + 1;
    int j = x % m;
    if (j == 0)
        j = m;
    return make_pair(i, j);
}

inline bool Verify(int i, int j)
{
    return 1 <= i && i <= n && 1 <= j && j <= m;
}

int main()
{
    ifstream fin("castel.in");
    ofstream fout("castel.out");
    fin >> n >> m >> k;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
            fin >> a[i][j];
    pair <int, int> aux = Convert2(k);
    viz[aux.first][aux.second] = true;
    q.push(k);
    int i, j, x, y, k;
    while (!q.empty())
    {
        int val = q.front();
        q.pop();
        have[val] = true;
        if (!tried[val].empty())
        {
            while (!tried[val].empty())
            {
                aux = Convert2(tried[val].back());
                if (viz[aux.first][aux.second] == false)
                {
                    viz[aux.first][aux.second] = true;
                    q.push(tried[val].back());
                }
                tried[val].pop_back();
            }
        }
        aux = Convert2(val);
        for (k = 0;k < 4;++k)
        {
            x = aux.first + dx[k];
            y = aux.second + dy[k];
            if (Verify(x, y) && viz[x][y] == false)
            {
                int posaux = Convert1(x, y);
                if (have[a[x][y]] == true)
                {
                    viz[x][y] = true;
                    have[posaux] = true;
                    q.push(posaux);
                }
                else
                {
                    tried[a[x][y]].push_back(posaux);
                }
            }

        }
    }
    int cnt = 0;
    for (int i = 1;i <= n;++i)
        for (int j = 1;j <= m;++j)
            cnt += viz[i][j];
    fout << cnt << "\n";
    fin.close();
    fout.close();
    return 0;
}