Cod sursa(job #1690016)

Utilizator Athena99Anghel Anca Athena99 Data 14 aprilie 2016 18:10:00
Problema Castel Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.89 kb
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int nmax= 150;
const int vmax= nmax*nmax;
const int dx[]= {0, 0, 1, -1};
const int dy[]= {1, -1, 0, 0};

bool f[vmax+1], u[nmax+1][nmax+1];
int v[nmax+1][nmax+1];

queue <int> q;
vector <int> key[vmax+1];

void turn( int k, int &x, int &y, int m ) {
    x= k/m+1, y= k%m;
    if ( y==0 ) {
        --x, y= m;
    }
}

int main(  ) {
    int n, m, k;
    fin>>n>>m>>k;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            fin>>v[i][j];
            key[v[i][j]].push_back((i-1)*m+j);
        }
    }

    f[k]= 1;
    for ( q.push(k); !q.empty(); q.pop() ) {
        int x, y;
        turn(q.front(), x, y, m);
        u[x][y]= 1;

        for ( int i= 0, a, b; i<(int)key[q.front()].size(); ++i ) {
            turn(key[q.front()][i], a, b, m);
            for ( int l= 0, d, s; l<4; ++l ) {
                d= a+dx[l], s= b+dy[l];
                if ( d>=1 && s>=1 && d<=n && s<=m && u[d][s]==1 ) {
                    u[a][b]= 1;
                    q.push(key[q.front()][i]);
                    f[key[q.front()][i]]= 1;

                    key[q.front()][i]= key[q.front()].back();
                    key[q.front()].pop_back();
                    --i;
                    break;
                }
            }
        }

        for ( int l= 0; l<4; ++l ) {
            int a= x+dx[l], b= y+dy[l];
            if ( a>=1 && b>=1 && a<=n && b<=m && f[v[a][b]]==1 && u[a][b]==0 ) {
                u[a][b]= 1;
                q.push((a-1)*m+b);
                f[(a-1)*m+b]= 1;
            }
        }
    }

    int sol= 0;
    for ( int i= 1; i<=n; ++i ) {
        for ( int j= 1; j<=m; ++j ) {
            sol+= u[i][j];
        }
    }

    fout<<sol<<"\n";

    return 0;
}