Pagini recente » Cod sursa (job #2278565) | Cod sursa (job #2857449) | Cod sursa (job #10313) | Cod sursa (job #2110276) | Cod sursa (job #682025)
Cod sursa(job #682025)
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#define MAX 155
using namespace std;
int n, m, start, total;
int matrice[MAX][MAX];
bool parcurs[MAX][MAX];
bool chei[MAX * MAX];
int depl_x[] = {-1, 0, 1, 0};
int depl_y[] = {0, 1, 0, -1};
struct coada
{
int x, y, cod;
};
vector<coada> visit;
map<int, vector<coada> > unopened;
vector<coada> adauga;
void citire()
{
freopen("castel.in", "r", stdin);
scanf("%d %d %d", &n, &m, &start);
int i, j;
for(i = 1; i <= n; i++)
{
for(j = 1; j <= m; j++)
{
scanf("%d", &matrice[i][j]);
}
}
total = 1;
fclose(stdin);
}
void deschide(int cheie)
{
unsigned int i;
if(unopened.count(cheie))
{
for(i = 0; i < unopened[cheie].size(); i++)
{
visit.push_back(unopened[cheie][i]);
chei[unopened[cheie][i].cod] = true;
parcurs[unopened[cheie][i].x][unopened[cheie][i].y] = true;
deschide(unopened[cheie][i].cod);
}
}
unopened.erase(cheie);
}
void solve()
{
chei[start] = true;
coada adaugare;
adaugare.x = start / m + 1;
adaugare.y = start % m;
if(!adaugare.y)
{
adaugare.x--;
adaugare.y = m;
}
adaugare.cod = start;
parcurs[adaugare.x][adaugare.y] = true;
visit.push_back(adaugare);
unsigned int a = 0;
int i;
while(a < visit.size())
{
for(i = 0; i != 4; i++)
{
if(visit[a].x + depl_x[i] > 0 && visit[a].x + depl_x[i] <= n &&
visit[a].y + depl_y[i] > 0 && visit[a].y + depl_y[i] <= m &&
!parcurs[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]])
{
if(chei[matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]]])
{
adaugare.x = visit[a].x + depl_x[i];
adaugare.y = visit[a].y + depl_y[i];
adaugare.cod = m * (adaugare.x - 1) + adaugare.y;
parcurs[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]] = true;
chei[adaugare.cod] = true;
visit.push_back(adaugare);
deschide(adaugare.cod);
}
else
{
adaugare.x = visit[a].x + depl_x[i];
adaugare.y = visit[a].y + depl_y[i];
adaugare.cod = m * (adaugare.x - 1) + adaugare.y;
parcurs[adaugare.x][adaugare.y] = true;
if(unopened.count(matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]]))
{
unopened[matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]]].push_back(adaugare);
}
else
{
adauga.push_back(adaugare);
unopened.insert(pair<int, vector<coada> >(matrice[visit[a].x + depl_x[i]][visit[a].y + depl_y[i]], adauga));
adauga.clear();
}
}
}
}
a++;
}
}
void afisare()
{
freopen("castel.out", "w", stdout);
printf("%d", visit.size());
fclose(stdout);
}
int main()
{
citire();
solve();
afisare();
return 0;
}