Pagini recente » Cod sursa (job #2052475) | Cod sursa (job #2070297) | Cod sursa (job #3139707) | Cod sursa (job #344328) | Cod sursa (job #1793193)
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
queue< pair<int,int> >coada;
int M[151][151];
int A[151][151];
bool a[151][151];
int v[22501];
int dx[4]={0,0,-1,1};
int dy[4]={-1,1,0,0};
int n,m,k;
void put(int x)
{
int i=1;
while(i<=k and v[i]<x)
i++;
if(i<=k)
{
int j;
for(j=k;j>=i;j--)
v[j+1]=v[j];
}
v[i]=x;
k++;
}
bool CB(int x)
{
int p=1,q=k;
if(x<v[p] or x>v[q]) return false;
else
{
while(p<=q)
{
int mjl=(p+q)/2;
if(v[mjl]==x) return true;
else
{
if(v[mjl]<x) p=mjl+1;
else q=mjl-1;
}
}
return false;
}
}
bool ok(int x, int y)
{
if(x<1 or y<1 or x>n or y>m) return false;
if(a[x][y]==0)
{int val=M[x][y];
return CB(val);
}
return false;
}
void Lee(int x, int y)
{
int i,j,iu,ju,con;
coada.push(make_pair(x,y));
while(!coada.empty())
{
i=coada.front().first;
j=coada.front().second;
coada.pop();
for(con=0;con<=3;con++)
{
iu=i+dx[con];
ju=j+dy[con];
if(ok(iu,ju))
{
a[iu][ju]=true;
coada.push(make_pair(iu,ju));
put(A[iu][ju]);
}
}
}
}
int main()
{int i,j,pozin,nr=0,x,y;
f>>n>>m>>pozin;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
f>>M[i][j];
A[i][j]=++nr;
if(nr==pozin){x=i; y=j;}
}
v[++k]=pozin;
a[x][y]=true;
Lee(x,y);
nr=0;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(a[i][j]) Lee(i,j);
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
nr+=a[i][j];
g<<nr;
return 0;
}