Cod sursa(job #1329671)

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

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

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 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();
    ok[k] = 1;
    coada.push(k);
}

void bfs()
{

    int c;
    while(!coada.empty()){
        c = coada.front();
        int i,j;
        convert(c,i,j);
        if(!nr[i][j]){
            ++sol;
            nr[i][j] = 1;
        }
        for(int x = 0 ; x < 4 ; x++){
            int new_x = i + d1[x];
            int new_y = j + d2[x];
            if(!viz[new_x][new_y] && ok[v[new_x][new_y]] && new_x > 0 && new_x <= n && new_y > 0 && new_x <= m){
                viz[new_x][new_y] = 1;
                int p = cod(new_x,new_y);
                coada.push(p);
                for(int l = 0 ; l < key[p].size(); l++){
                    coada.push(key[p][l]);
                    ok[key[p][l]] = 1;
                }
                ok[cod(new_x,new_y)] = 1;
            }
            else if(!viz[new_x][new_y] && !ok[v[new_x][new_y]] && new_x > 0 && new_x <= n && new_y > 0 && new_x <= m){
                key[v[new_x][new_y]].push_back(cod(new_x,new_y));
                viz[new_x][new_y] = 1;
            }
        }
        coada.pop();
    }
    out<<sol;
}

int main()
{

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