Pagini recente » Cod sursa (job #681847) | Cod sursa (job #1814336) | Cod sursa (job #951436) | Cod sursa (job #1071695) | Cod sursa (job #2269330)
#include <fstream>
#include <queue>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
queue<pair<int, int> >q;
int di[] = {1, 0, -1, 0};
int dj[] = {0, 1, 0, -1};
int room[160][160];
int key[160][160];
int keys[22500];
int n, m, k;
int liPr, coPr, nrKeys;
void citire();
void lee(int);
bool ifkey(int, int);
void afisare_matrice();
int main()
{
citire();
keys[nrKeys] = room[liPr][coPr];
nrKeys++;
bool ok = true;
int visit = -1;
//afisare_matrice();
while (ok == true)
{
int aux = nrKeys;
lee(visit);
visit--;
//afisare_matrice();
if (nrKeys == aux) ok = false;
}
//afisare_matrice();
g << nrKeys;
return 0;
}
void citire()
{
f >> n >> m >> k;
int x = 1;
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
f >> key[i][j];
room[i][j] = x;
x++;
if (room[i][j] == k)
{
liPr = i;
coPr = j;
}
}
}
}
void bordare()
{
for (int i = 0; i <= n+1; i++)
{
room[i][0] = 0;
room[i][m+1] = 0;
}
for (int j = 0; j <= m+1; j++)
{
room[0][j] = 0;
room[n+1][j] = 0;
}
}
bool ifkey(int x, int y)
{
for (int i = 0; i < nrKeys; i++)
if (key[x][y] == keys[i])
return true;
return false;
}
void lee(int visit)
{
room[liPr][coPr] = visit;
q.push(make_pair(liPr, coPr));
while(!q.empty())
{
pair<int, int>p = q.front();
q.pop();
for (int k = 0; k < 4; k++)
{
if (room[p.first+di[k]][p.second+dj[k]] > 0 && ifkey(p.first+di[k], p.second+dj[k]) == true)
{
keys[nrKeys] = room[p.first+di[k]][p.second+dj[k]];
nrKeys++;
room[p.first+di[k]][p.second+dj[k]] = visit-1;
q.push(make_pair(p.first+di[k], p.second+dj[k]));
}
else if (room[p.first+di[k]][p.second+dj[k]] == visit)
{
room[p.first+di[k]][p.second+dj[k]] = visit-1;
q.push(make_pair(p.first+di[k], p.second+dj[k]));
}
}
}
}
void afisare_matrice()
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
g << room[i][j] << " ";
g << "\n";
}
g << "\n" << nrKeys;
g << "\n\n";
}