Cod sursa(job #1167586)

Utilizator YoChinezuWeng Mihai Alexandru YoChinezu Data 5 aprilie 2014 15:18:10
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include <cstdio>
#include <queue>
#include <set>
#include <bitset>

using namespace std;

queue <int> Q;
bool  v[22505][22505];
int a[155][155],cc,ll;
int dx[]= {-1,0,1,0},
          dy[]= {0,1,0,-1};
bitset <22505> f;

inline int conv1(int l,int c,int m) {
    return (l-1)*m+c;
}

inline void conv2(int k,int n,int m) {
    ll=k/m+(k%m!=0);
    cc=k%m+(k%m==0?m:0);
}

int main() {
    freopen("castel.in","r",stdin);
    freopen("castel.out","w",stdout);

    int n,m,k,aux,new_x,new_y,l,c,Size,temp,rasp=0;
    scanf("%d%d%d",&n,&m,&k);

    for(register int i=1; i<=n; ++i) {
        for(register int j=1; j<=m; ++j) {
            scanf("%d",&a[i][j]);
        }
    }
    Size=22505;

    Q.push(k);

    while(!Q.empty()) {
        aux=Q.front();
        ++rasp;
        conv2(aux,n,m);
        f[aux]=1;
        //printf("%d ",aux);
        for(register int i=0; i<4; ++i) {
            new_x=dx[i]+ll;
            new_y=dy[i]+cc;
            if(a[new_x][new_y]!=0 && f[conv1(new_x, new_y, m)] == 0) {

                for(int j=1; j<=Size; ++j) {
                    if(v[aux][j]==1) {
                        v[aux][j]=0;
                        if(f[j]==0) {
                            f[j]=1;
                            Q.push(j);
                        }
                    }
                }

                temp=conv1(new_x,new_y,m);
                if(f[a[new_x][new_y]]==1) {
                    Q.push(temp);
                    f[temp]=1;
                } else {
                    v[a[new_x][new_y]][temp]=1;
                }
            }
        }

        Q.pop();
    }

    printf("%d",rasp);
    /*for(int i=0; i<=12; ++i) {
        if(f.test(i)) {
            printf("1 ");
        } else
            printf("0 ");
    }*/

    return 0;
}