Cod sursa(job #2148917)

Utilizator AlexandruLuchianov1Alex Luchianov AlexandruLuchianov1 Data 2 martie 2018 09:57:12
Problema Castel Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

int n , m;
#define code(i , j) ((i - 1) * m + j)
#define getx(i) (i / m + 1)
#define gety(i) ((i - 1) % m + 1)

bool valid(int x , int y){
  return (1 <= x && x <= n) && (1 <= y && y <= m);
}
struct Cube{
  int x;
  int y;
};
int const nmax = 150;
int const iplus[4] = {0 , 0 , 1 , -1};
int const jplus[4] = {1 , -1 , 0 , 0};

vector <Cube> g[5 + nmax * nmax];
int open[5 + nmax][5 + nmax];
///1 - open
///2 - in queue
///3 - already solved

int main()
{
  int k;
  in>>n>>m>>k;
  for(int i = 1 ; i <= n ;i++){
    for(int j = 1 ; j <= m ;j++){
      int a;
      in>>a;
      g[a].push_back({i , j});
    }
  }
  queue<Cube> q;
  q.push({getx(k) , gety(k)});
  open[getx(k)][gety(k)] = 2;

  int sum = 0;
  while(0 < q.size()){
    int x = q.front().x;
    int y = q.front().y;
    k = code(x , y);
    q.pop();
    if(open[x][y] == 2){
      open[x][y] = 3;
      sum++;
      for(int i = 0 ; i < g[k].size() ; i++){
        int x2 = g[k][i].x;
        int y2 = g[k][i].y;
        if(open[x2][y2] == 0){
          open[x2][y2] = 1;
          for(int h = 0 ; h < 4 ;h++){
            int newx = x2 + iplus[h];
            int newy = y2 + jplus[h];
            if(valid(newx , newy) && open[newx][newy] == 3){
              open[x2][y2] = 2;
              q.push({x2 , y2});
            }
          }
        }
      }
      for(int h = 0 ; h < 4 ;h++){
        int newx = x + iplus[h];
        int newy = y + jplus[h];
        if(valid(newx , newy) && open[newx][newy] == 1){
          open[newx][newy] = 2;
          q.push({newx , newy});
        }
      }
    }
  }
  out<<sum;
  return 0;
}