Pagini recente » Cod sursa (job #2478695) | Cod sursa (job #2360594)
#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;
}