Pagini recente » Monitorul de evaluare | Istoria paginii utilizator/rotaru_jeni_323cb | Istoria paginii utilizator/siscan | Monitorul de evaluare | Cod sursa (job #609518)
Cod sursa(job #609518)
#include <fstream>
#include <vector>
using namespace std;
const int N=22501;
int v[N],stack[N],vecin[5],n,m,nr;
bool use[4*N],acc[N];
vector<int> need[N];
ifstream in("castel.in");
ofstream out("castel.out");
inline void push(int x)
{
stack[++stack[0]]=x;
}
inline void pop(int& x)
{
x=stack[stack[0]--];
}
inline void det(int x)
{
vecin[0]=0;
if (x>m)
vecin[++vecin[0]]=x-m;
if (x<=(n-1)*m)
vecin[++vecin[0]]=x+m;
if (x%m)
vecin[++vecin[0]]=x+1;
if (x%m!=1)
vecin[++vecin[0]]=x-1;
}
void bfs(int x)
{
push(x);
while (stack[0])
{
pop(x);
if (use[x])
continue;
use[x]=true;
nr++;
for (vector<int>::iterator i=need[x].begin();i!=need[x].end();i++)
if (!use[*i] && acc[*i])
push(*i);
det(x);
for (int i=1;i<=vecin[0];i++)
{
acc[vecin[i]]=true;
if (!use[vecin[i]] && use[v[vecin[i]]])
push(vecin[i]);
}
}
}
int main()
{
int S;
in>>n>>m>>S;
for (int i=1;i<=n*m;i++)
{
in>>v[i];
need[v[i]].push_back(i);
}
bfs(S);
out<<nr<<"\n";
}