Cod sursa(job #1411023)

Utilizator nacrocRadu C nacroc Data 31 martie 2015 13:21:15
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.43 kb
#include <stdio.h>
#include <queue>
#include <set>
#define NMAX 155

//pozitie = (i-1)*M + j

using namespace std;

struct poz{
    int x, y;
};

int mat[NMAX][NMAX];
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
queue < pair <int, int> > q;
int N, M, x, y;

set <int> s;

void lee(){
    poz p;
    int nr = 0;
    q.push(make_pair(x, y));
    while(!q.empty()){
        p.x = q.front().first;
        p.y = q.front().second;
        q.pop();
        if(s.find((p.x-1)*M + p.y) == s.end()){
            s.insert((p.x-1)*M + p.y);
            nr = 0;
        }
        else ++nr;
        if(nr == 100000) break;
        for(int k = 0; k <= 3; ++k)
            if(mat[p.x+dx[k]][p.y+dy[k]] != -1 && s.find(mat[p.x+dx[k]][p.y+dy[k]]) != s.end())
                q.push(make_pair(p.x+dx[k], p.y+dy[k]));
    }

}

void bordare(int N, int M){
    for(int i = 0; i <= N+1; ++i)
        mat[i][0] = mat[i][M+1] = -1;
    for(int i = 0; i <= M+1; ++i)
        mat[0][i] = mat[N+1][i] = -1;
}

int main(){
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
    int K;
    scanf("%d %d %d", &N, &M, &K);
    x = 1;
    y = 0;
    while(x*M < K)
        ++x;
    while((x-1)*M+y < K)
        ++y;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            scanf("%d", &mat[i][j]);
    bordare(N, M);
    lee();
    printf("%d\n", s.size());
    return 0;
}