Cod sursa(job #1793193)

Utilizator tifui.alexandruTifui Ioan Alexandru tifui.alexandru Data 30 octombrie 2016 20:17:27
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#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;
}