Cod sursa(job #2757624)

Utilizator VipioanaMirea Oana Teodora Vipioana Data 5 iunie 2021 15:52:21
Problema Castel Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.26 kb
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream f("castel.in");
ofstream g("castel.out");
int n,m,k,i,j,nrc,x,y,rez,d;
int a[151][151];
bool nrcam[151*151],vf[151*151];
queue <int> q;

vector <int> v[22505];
int dx[]= {-1,0,1,0};
int dy[]= {0,1,0,-1};

/*bool isValid(int i, int j) {
  return (i>=1 && j>=1 && i<=n && j<=m);
}

bool isSafe(int i, int j) {
  return vf[a[i][j]];
}*/

void back()
{
  if(q.empty())
    return;

  nrc=q.front();
  q.pop();
  i=nrc/m;
  if(nrc%m!=0)
    i++;
  j=nrc%m;
  if(nrc%m==0)
    j=m;
  vf[nrc]=true;
  rez++;
  for(d=0; d<v[nrc].size(); d++)
  {
    if(!nrcam[v[nrc][d]])
      q.push(v[nrc][d]);
    nrcam[v[nrc][d]]=true;
  }
  v[nrc].clear();
  for(d=0; d<4; d++)
  {
      x=i+dx[d];
      y=j+dy[d];
      nrc=(x-1)*m+y;
      if(x>=1 && x<=n && y>=1 && y<=m)
      {
          if(!nrcam[nrc] && vf[a[x][y]])
        {
            nrcam[nrc]=true;
            q.push(nrc);
        }
      else
        v[a[x][y]].push_back(nrc);
      }
  }
    back();
}

  int main() {
    f>>n>>m>>k;
    for(i=1; i<=n; i++)
      for(j=1; j<=m; j++)
        f>>a[i][j];
    q.push(k);
    nrcam[k]=true;
    back();
    g<<rez;
    return 0;
  }