Cod sursa(job #59716)

Utilizator flo_demonBunau Florin flo_demon Data 10 mai 2007 11:23:30
Problema Castel Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.2 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 inou, jnou;
    has_key[k] = true;
    has_key[  a[get_line(k)][get_col(k)]  ] = true;
    marked[get_line(k)][get_col(k)] = true;
    
    bool found = true;
    while (found)
    {
        found = false;
        for (int ii = 1; ii <= n; ++ii)
            for (int jj = 1; jj <= m; ++jj)
                if (marked[ii][jj])
                { 
                    for (int d = 0; d < 4; ++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;
                            found = true;
                        }   
                        if (found) break;  
                    }   
                    if (found) break; 
                }    
    }        
}    

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;
}