Cod sursa(job #2145816)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 27 februarie 2018 17:12:05
Problema Castel Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.02 kb
#include <fstream>
#include <vector>
#include <queue>
#include <bitset>

using namespace std;

ifstream in("castel.in");
ofstream out("castel.out");

const int MAXNM = 150;
const int MAXK = MAXNM * MAXNM;

vector <int>g[MAXNM + 2];
bitset <MAXK + 2>open;
bitset <MAXK + 2>viz;
int mat[MAXNM + 2][MAXNM + 2];

int n, m, start;
vector <pair <int, int> >nxt;

void bfs(int cheie){
  queue <int>nodes;
  nodes.push(cheie);
  open[cheie] = 1;

  while (nodes.size()){
    for (auto x : g[nodes.front()]){
      if (!open[x]){
        open[x] = 1;
        nodes.push(x);
      }
    }
    nodes.pop();
  }
}

pair <int, int>ret_cor(int camera){
  pair <int, int>cor;
  camera --;

  cor.first = camera / m;
  cor.second = camera % m + 1;

  return cor;
}

int ret_cam(pair <int, int>ceva){
  int cam;
  cam = ceva.first * m + ceva.second;
  return cam;
}

int in_limits(int camera){
  if (camera > 0 && camera <= n * m)
    return true;
  return false;
}

int fil(int camera){
  int cnt = 1;
  viz[camera] = true;
  pair <int, int>cor = ret_cor(camera);
  queue <int>coada;
  coada.push(camera);

  while (coada.size()){
    cor = ret_cor(coada.front());

    for (auto x : nxt){
      if (open[mat[cor.first + x.first][cor.second + x.second]] && !viz[ret_cam({cor.first + x.first, cor.second + x.second})] && in_limits(ret_cam({cor.first + x.first, cor.second + x.second}))){
        viz[ret_cam({cor.first + x.first, cor.second + x.second})] = 1;
        coada.push(ret_cam({cor.first + x.first, cor.second + x.second}));
        cnt ++;
      }
    }

    coada.pop();

  }

  return cnt;
}

int main(){
  nxt.push_back({1, 0});
  nxt.push_back({-1, 0});
  nxt.push_back({0, 1});
  nxt.push_back({0, -1});

  in >> n >> m >> start;

  for (int i = 1; i <= n * m; ++ i){
    int cheie;
    in >> cheie;

    pair <int, int>cor = ret_cor(i);
    mat[cor.first][cor.second] = cheie;

    g[cheie].push_back(i);
  }

  bfs(start);

  //out << fil(start);


  return 0;
}