Cod sursa(job #1489043)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 20 septembrie 2015 14:58:53
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.h>
#include <unistd.h>

using namespace std;

const int MAX_N = 150;
const int INF = 0x3F3F3F3F;
const int NUM_DIR = 4;
const int dir[][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } };

int key[MAX_N + 2][MAX_N + 2];
bool seen[MAX_N + 2][MAX_N + 2];

vector < pair < int, int > > solveNext[MAX_N + 1][MAX_N + 1];

queue < pair <int, int> > Q;

int n, m;

inline pair <int, int> getInd(const int &x)
{
    return { (x - 1) / m + 1, x - (x - 1) / m * m };
}

int main()
{
    ifstream in("castel.in");
    ofstream out("castel.out");
    int start;

    in >> n >> m >> start;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            in >> key[i][j];
    in.close();

    for (int i = 0; i <= n + 1; i++)
        key[i][0] = key[i][m + 1] = INF;
    for (int i = 0; i <= m + 1; i++)
        key[0][i] = key[n + 1][i] = INF;

    Q.push(getInd(start));
    int cnt = 0;
    do
    {
        pair <int, int> ind = Q.front();
        Q.pop();

        if (seen[ind.first][ind.second])
            continue;

        cnt++;
        seen[ind.first][ind.second] = 1;

        for (auto p : solveNext[ind.first][ind.second])
            Q.push(p);

        for (int i = 0; i < NUM_DIR; i++)
        {
            pair <int, int> newInd = { ind.first + dir[i][0], ind.second + dir[i][1] };

            if (key[newInd.first][newInd.second] == INF)
                continue;

            pair <int, int> newKey = getInd(key[newInd.first][newInd.second]);

            if (seen[newKey.first][newKey.second])
                Q.push(newInd);
            else
                solveNext[newKey.first][newKey.second].emplace_back(newInd);
        }
    } while (!Q.empty());
    out << cnt << '\n';
    out.close();
    return 0;
}