Cod sursa(job #597077)

Utilizator MarcvsHdrMihai Leonte MarcvsHdr Data 21 iunie 2011 07:04:10
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.69 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

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

#define MAXN 151

#define PACK(i,j) (((i)-1)*m+(j))
#define ROW(c) (((c)-1)/m+1)
#define COL(c) (((c)-1)%m+1)

int n,m,k,sol;
deque<int> wait_queue[MAXN*MAXN+1];

int used[MAXN][MAXN];
int key[MAXN][MAXN];

int vi[4] = { -1, 0, 1, 0};
int vj[4] = { 0, 1, 0, -1};

int main()
{
   /* citire date de intrare */
   in >> n >> m >> k;
   for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
         in >> key[i][j];
      }
   }

   /* facem explorarea */
   deque<int> q;
   q.push_back(k);
   int newi, newj;
   while (!q.empty()){
      k = q.front();
      q.pop_front();
      if (used[ROW(k)][COL(k)]) {
         continue; 
      }
      sol++;
      used[ROW(k)][COL(k)] = 1;
      for (int dir = 0; dir < 4; ++dir) {
         newi = ROW(k) + vi[dir];
         newj = COL(k) + vj[dir];
         if (newi >= 1 && newj >= 1 && newi <= n && newj <= m &&
               !used[newi][newj]) {
            /* avem sau nu cheie, oare? */
            if (used[ROW(key[newi][newj])][COL(key[newi][newj])]) {
               /* pune la coada q */
               q.push_back(PACK(newi,newj));
            } else {
               /* pune la o coada de asteptare */
               wait_queue[key[newi][newj]].push_back(PACK(newi,newj));
            }
         }
      }
      /* muta in coada de asteptare generala pe cei ce asteptau */
      while (wait_queue[k].empty() == false) {
         q.push_back(wait_queue[k].front());
         wait_queue[k].pop_front();
      }
   }

   out << sol << "\n";

   out.close();
   in.close();

   return 0;
}