Pagini recente » Cod sursa (job #2435089) | Cod sursa (job #2090800) | Cod sursa (job #2208265) | Cod sursa (job #1557087) | Cod sursa (job #1489045)
#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;
}