Cod sursa(job #1958983)

Utilizator hrazvanHarsan Razvan hrazvan Data 8 aprilie 2017 22:57:41
Problema Castel Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.65 kb
#include <cstdio>
#include <cstring>
#define MAXN 150
char r1[MAXN][MAXN], r2[MAXN][MAXN];
int q[MAXN * MAXN], ma[MAXN][MAXN], sq, dq;
int ut[MAXN * MAXN + 1], nxt[MAXN * MAXN];
char p[MAXN * MAXN + 1];
int rez;
int n, m;
int d[4][2] = {{0, 1}, {1, 0}, {-1, 0}, {0, -1}};

inline void utd(int k, int &x, int &y){
  x = k / m;
  y = k % m;
}

inline void caut(){
  int x, y, i, nx, ny, poz, cx, cy;
  while(sq < dq){
    rez++;
    utd(q[sq++], x, y);
    for(i = 0; i < 4; i++){
      nx = x + d[i][0];
      ny = y + d[i][1];
      if(nx >= 0 && nx < n && ny >= 0 && ny < m){
        if(r2[nx][ny] == 1 && r1[nx][ny] == 0){
          q[dq++] = nx * m + ny;
          poz = ut[nx * m + ny];
          while(poz != -1){
            utd(poz, cx, cy);
            r2[cx][cy] = 1;
            if(r1[cx][cy] == 1){
              q[dq++] = poz;
            }
            poz = nxt[poz];
          }
          p[ma[nx][ny]] = 1;
        }
        r1[nx][ny] = 1;
      }
    }
  }
}

int main(){
  FILE *in = fopen("castel.in", "r");
  int k, i, x, y, j, poz;
  fscanf(in, "%d%d%d", &n, &m, &k);
  memset(ut, -1, sizeof ut);
  for(i = 0; i < n; i++){
    for(j = 0; j < m; j++){
      fscanf(in, "%d", &ma[i][j]);
      ma[i][j]--;
      nxt[i * m + j] = ut[ma[i][j]];
      ut[ma[i][j]] = i * m + j;
    }
  }
  fclose(in);
  q[0] = k - 1;
  dq = 1;
  utd(k - 1, x, y);
  poz = ut[ma[x][y]];
  r1[x][y] = r2[x][y] = 1;
  p[ma[x][y]] = 1;
  while(poz != -1){
    utd(poz, x, y);
    r2[x][y] =1;
    poz = nxt[poz];
  }
  caut();
  FILE *out = fopen("castel.out", "w");
  fprintf(out, "%d", rez);
  fclose(out);
  return 0;
}