Cod sursa(job #1329716)

Utilizator radu_cebotariRadu Cebotari radu_cebotari Data 29 ianuarie 2015 19:53:22
Problema Castel Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.71 kb
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
ifstream in("castel.in");
ofstream out("castel.out");
const int NMAX = 200;

vector<int> key[NMAX * NMAX + 5];
int viz[NMAX * NMAX + 5],n,m,k,v[NMAX + 5][NMAX + 5],sol;
int d1[] = {1,0,-1,0};
int d2[] = {0,1,0,-1};
queue<int> coada;

void read()
{

    in>>n>>m>>k;
    for(int i = 1 ; i <= n ; i++)
        for(int j = 1 ; j <= m ; j++)
            in>>v[i][j];
    in.close();
    coada.push(k);
    viz[k] = 1;
}

void convert(int val,int &i,int &j)
{

    i = val/m;
    j = (val + m) % m;
    if(j == 0)
        j = m;
    else
        ++i;
}

int cod(int i,int j)
{

    return (i-1)*m + j;
}

void bfs()
{

    int c;
    while(!coada.empty()){
        c = coada.front();
        int i,j;
        convert(c,i,j);
        for(int o = 0 ; o < key[c].size() ; ++o)
            if(!viz[key[c][o]]){
                viz[key[c][o]] = 1;
                coada.push(v[c][o]);
            }
        key[c].clear();
        for(int l = 0 ; l < 4 ; l++){
            int new_i = i + d1[l];
            int new_j = j + d2[l];
            if(new_i < 1 || new_i > n || new_j < 1 || new_j > m)
                continue;
            if(!viz[cod(new_i,new_j)]){
                if(viz[v[new_i][new_j]]){
                    viz[cod(new_i,new_j)] = 1;
                    coada.push(cod(new_i,new_j));
                }
                else
                    key[v[new_i][new_j]].push_back(cod(new_i,new_j));
            }
        }
        coada.pop();
    }

    for(int i = 1 ; i <= n*m ; i++)
        if(viz[i])
            ++sol;
    out<<sol;
}

int main()
{

    read();
    bfs();
    return 0;
}