Cod sursa(job #1268161)

Utilizator smaraldaSmaranda Dinu smaralda Data 20 noiembrie 2014 17:48:15
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;

#define ITERATOR vector<int>::iterator
const int NMAX = 155;

queue <int> q;
vector <int> onHold[NMAX * NMAX];
int n, m, grid[NMAX][NMAX], di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};
bool vis[NMAX * NMAX];

void decode (int x, int &i, int &j) {
    i = x / m;
    j = x % m;
    if(j == 0)
        j = m;
    else
        ++ i;
}

int code (int i, int j) {
    return (i - 1) * m + j;
}

bool inBound (int i, int j) {
    return i >= 1 && j >= 1 && i <= n && j <= m;
}

void expand (int room) {
    int i, j, newi, newj, k;
    ITERATOR it;

    decode(room, i, j);
    for(it = onHold[room].begin(); it != onHold[room].end(); ++ it)
        if(!vis[*it]) {
            q.push(*it);
            vis[*it] = 1;
        }
    onHold[room].clear();

    for(k = 0; k < 4; ++ k) {
        newi = i + di[k];
        newj = j + dj[k];
        if(!vis[code(newi, newj)]) {
            if(vis[grid[newi][newj]])
                q.push(code(newi, newj)),
                vis[code(newi, newj)] = 1;
            else
                onHold[grid[newi][newj]].push_back(code(newi, newj));
        }
    }
}

int main() {
    freopen("castel.in", "r", stdin);
    freopen("castel.out", "w", stdout);
    int i, j, room, cnt, k, newi, newj, change;

    scanf("%d%d%d", &n, &m, &room);
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= m; ++ j)
            scanf("%d", &grid[i][j]);

    q.push(room);
    vis[room] = 1;
    while(!q.empty()) {
        expand(q.front());
        q.pop();
    }

    cnt = 0;
    for(i = 1; i <= n * m; ++ i)
        if(vis[i])
            ++ cnt;

    printf("%d\n", cnt);
    return 0;
}