Cod sursa(job #867543)

Utilizator DaNutZ2UuUUBB Bora Dan DaNutZ2UuU Data 29 ianuarie 2013 20:25:58
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include<fstream>
#include<vector>
#include<queue>
#define NMAX 160
 
using namespace std;
 
ifstream f("castel.in");
ofstream g("castel.out");
 
int a[NMAX][NMAX], n, m, k, nr=0;
int di[4]={0, 0, -1, 1};
int dj[4]={-1, 1, 0, 0};
bool chei[22501], vz[NMAX][NMAX], ad[NMAX][NMAX];
 
queue<int> q;
vector<int> v[22501];
 
void Citeste()
{
    int i, j;
    f>>n>>m>>k;
    for (i=1; i<=n; ++i)
        for (j=1; j<=m; ++j) f>>a[i][j];
    for (i=0; i<=n+1; ++i) a[i][0]=a[i][m+1]=-1;
    for (j=0; j<=m+1; ++j) a[0][j]=a[n+1][j]=-1;
}
 
void Adauga(int i, int j)
{
    int k, val=(i-1)*m+j;
    ++nr;
    vz[i][j]=1; chei[val]=1; q.push(i*1000+j);
    for (k=0; k<(int)v[val].size(); ++k) Adauga(v[val][k]/1000, v[val][k]%1000);
}
 
void Solve()
{
    int sti, stj, r, i, j, ii, jj, kk;
    sti=k/m;
    if (k%m!=0) sti++;
    stj=k%m;
    if (stj==0) stj=m;
    Adauga(sti, stj);
    while(!q.empty())
    {
        r=q.front(); q.pop();
        i=r/1000; j=r%1000;
        for (kk=0; kk<4; ++kk)
        {
            ii=i+di[kk]; jj=j+dj[kk];
            if (!vz[ii][jj] && a[ii][jj]>0)
                if (chei[a[ii][jj]]) Adauga(ii, jj);
                else
                    if (!ad[ii][jj])
                    {
                        v[a[ii][jj]].push_back(ii*1000+jj);
                        ad[ii][jj]=1;
                    }
        }
    }
    g<<nr<<"\n";
}
 
int main()
{
    Citeste();
    Solve();
    f.close();
    g.close();
    return 0;
}