Cod sursa(job #1686257)

Utilizator alex.jilavu17alex jilavu alex.jilavu17 Data 12 aprilie 2016 10:03:54
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
#include <string.h>
using namespace std;
ifstream fin("castel.in");
ofstream fout("castel.out");
int k,m,n,a[151][151],xi,yi,v[22501],q,xc,yc,b[151][151],nrc,p,u;
const int dl[4]={0,0,-1,1};
const int dc[4]={1,-1,0,0};
struct element{
    int l,c,nr;}c[22501];
void cit(){
    fin>>m>>n>>k;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            fin>>a[i][j];
    xi=k/m+1;
    yi=k%n;
    if(yi==0)
        yi=n;
    q=1;
    v[1]=a[xi][yi];}
int poz(int i,int j){
    int i1,j1,i0=0,j0,aux;
    i1=i;
    j1=j;
    j0=-1;
    while(i1<j1){
        if(v[i1]>v[j1]){
            swap(v[i1],v[j1]);
            aux=-i0;
            i0=-j0;
            j0=aux;}
        i1+=i0;
        j1+=j0;}
    return i1;}
void quicksort(int i,int j){
    int k;
    if(i<j){
        k=poz(i,j);
        quicksort(i,k-1);
        quicksort(k+1,j);}}
void adauga(int x){
    q++;
    v[q]=x;}
int sub(int i,int j,int y){
    int m;
    if(i>j)
        return 0;
    m=(i+j)/2;
    if(v[m]==y)
        return m;
    if(y<v[m])
        return sub(i,m-1,y);
    return sub(m+1,j,y);}
int verif(int in,int jn){
    int k,y;
    quicksort(1,q);
    for(k=0;k<4;k++){
        y=a[in+dl[k]][jn+dc[k]];
        if(sub(1,q,y)!=0)
            return 1;}
    return 0;}
void Lee(){
    int i,j,in,jn,dn,d,h;
    p=u=1;
    nrc=1;
    c[p].l=xi;
    c[p].c=yi;
    c[p].nr=0;
    memset(b,-1,sizeof(b));
    b[xi][yi]=0;
    while(p<=u){
        i=c[u].l;
        j=c[u].c;
        d=c[u].nr;
        for(h=0;h<4;h++){
            in=i+dl[h];
            jn=j+dc[h];
            dn=d+1;
            if(in<m+1 && in>0 && jn<n+1 && jn>0 && verif(in,jn)==1){
                adauga(a[in][jn]);
                u++;
                if(b[in][jn]==-1)
                    nrc++;
                c[u].l=in;
                c[u].c=jn;
                c[u].nr=dn;
                b[in][jn]=dn;}}
        p++;}}
int main(){
    cit();
    Lee();
    fout<<nrc;
    return 0;}