Cod sursa(job #677804)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 10 februarie 2012 18:17:59
Problema Castel Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.25 kb
#include <fstream>
#include <deque>
#include <cstring>
#define NM 160
using namespace std;

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

const int dx[4]={-1,0,1,0};const int dy[4]={0,1,0,-1};
struct poz{int x,y;};poz mp(int a,int b){poz c;c.x=a;c.y=b;return c;}
deque<poz> D;
deque<poz> Lst[NM*NM];
int n,m,i,j,k,k1=0,li,ci,nec[NM][NM],viz[NM][NM],cheie[NM][NM];
int key[NM*NM],ANS=0;

void push(int l,int c) {
    if (l<1 || l>n) return;
    if (c<1 || c>m) return;
    if (viz[l][c]==1) return;
    if (key[nec[l][c]]==0) {Lst[nec[l][c]].push_back(mp(l,c));return;}
    viz[l][c]=1;
    D.push_back(mp(l,c));
}

int main () {
  f >> n >> m >> k;
  for (i=1;i<=n;i++) for (j=1;j<=m;j++)
      {cheie[i][j]=++k1;if (k1==k) li=i,ci=j;f >> nec[i][j];}
    D.push_back(mp(li,ci));viz[li][ci]=1;
    while(!D.empty()) {
      i=D.front().x;j=D.front().y;D.pop_front();
      key[cheie[i][j]]=1;
      int N=cheie[i][j];
      while(!Lst[N].empty()) {D.push_back(Lst[N].front());viz[Lst[N].front().x][Lst[N].front().y]=1;Lst[N].pop_front();}
      for (int d=0;d<4;d++)
        push(i+dx[d],j+dy[d]);
    }
  for (i=1;i<=n;i++)
    for (j=1;j<=m;j++)
      if (viz[i][j]>0) ANS++;
  g << ANS << '\n';
  f.close();g.close();
  return 0;
}