Cod sursa(job #59717)

Utilizator flo_demonBunau Florin flo_demon Data 10 mai 2007 11:24:35
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.26 kb
#include <stdio.h>
#include <iostream>
#include <queue>

using namespace std;

#define MAX 152

const int di[] = { -1, 0, 1, 0 };
const int dj[] = { 0, 1, 0, -1 }; 

struct stare {
    int i, j;
};    

stare aux;
int n, m, k, val;
int rez = 0;
int a[MAX][MAX];
bool has_key[MAX];
bool marked[MAX][MAX];

void bfs();
int get_line(int room);
int get_col(int room);
int get_room(int i, int j);

int main()
{
    FILE *fin = fopen("castel.in", "r");
    FILE *fout = fopen("castel.out", "w");
    fscanf(fin, "%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            fscanf(fin, "%d", &a[i][j]);
    bfs();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (marked[i][j])
                rez++;
    fprintf(fout, "%d\n", rez);
    
    fclose(fin);
    fclose(fout);
    
    return 0;
}    

void bfs()
{
    int ii, jj, inou, jnou;
    stare curr;
    queue<stare> Q;
    aux.i = get_line(k);
    aux.j = get_col(k);
    Q.push(aux);
    has_key[k] = true;
    has_key[a[aux.i][aux.j]] = true;
    marked[aux.i][aux.j] = true;
    
    while (!Q.empty())
    {
        curr = Q.front();
        Q.pop();
        ii = curr.i;
        jj = curr.j;
        for (int d = 0; d < 3; ++d)
        {
            inou = ii + di[d];
            jnou = jj + dj[d];
            if (inou >= 1 && jnou >= 1 && inou <= n && jnou <= m)
            if (has_key[ a[inou][jnou] ] && !marked[inou][jnou])
            {
                marked[inou][jnou] = true;
                has_key[ get_room(inou, jnou) ] = true;
                
                for (int iii = 1; iii <= n; ++iii)
                    for (int jjj = 1; jjj <= m; ++jjj)
                        if (marked[iii][jjj])
                        {
                            aux.i = iii;
                            aux.j = jjj;
                            Q.push(aux);
                        }    
            }    
        }    
    }  
}    

inline int get_line(int room)
{
   return ((room-1) / n) + 1;
}    

inline int get_col(int room)
{
    return (room - (get_line(room) - 1) * n) % (m + 1);
}    

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