Cod sursa(job #1489045)

Utilizator bciobanuBogdan Ciobanu bciobanu Data 20 septembrie 2015 15:04:59
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.8 kb
#include <bits/stdc++.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];
bitset <MAX_N + 2> seen[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++)
        seen[i][0] = seen[i][m + 1] = 1;
    for (int i = 0; i <= m + 1; i++)
        seen[0][i] = seen[n + 1][i] = 1;

    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])
            if (!seen[p.first][p.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 (seen[newInd.first][newInd.second])
                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;
}