Cod sursa(job #2990991)

Utilizator xDemonstyMatei Haba Ionut xDemonsty Data 8 martie 2023 20:54:34
Problema Castel Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <fstream>
#include <map>
#include <queue>
#include <vector>
using namespace std;
ifstream in("castel.in");
ofstream out("castel.out");

map<int,pair<int,int>> mp ;

queue<pair<int,int>> q;
bool conditie = true ;
long long n,m ;

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

int di [ ] = { 1, 0, -1, 0 };
int dj [ ] = { 0, -1, 0, 1 } ;
long long cheie [ 23000 ];
long long dist [ 151 ] [ 151 ];
long long mat [ 151 ][ 151 ];
long long lem [ 151 ] [ 151 ];
vector<pair<int,int>> lista ;

void lee ()
{
    while ( !q.empty() )
    {
        int i = q.front().first;
        int j = q.front().second ;

        dist [ i ] [ j ] = 1;

        if ( cheie [ lem [ i ] [ j ] ] == 0 )
            cheie [ lem [ i ] [ j ]] = 1;


        for ( int k = 0 ; k < 4 ; k ++ )
        {
            int iv = i + di [ k ] ;
            int jv = j + dj [ k ] ;

            if ( test ( iv, jv ) == true  && cheie [ mat [ iv ] [ jv ] ] != 0 && dist [ iv ] [ jv ] == 0  )
            {
                dist [ iv] [ jv ] = dist [ i ] [ j ] + 1;
                q.push({iv,jv});

            }
            else if ( dist [ iv ] [ jv ] == 0 && test ( iv, jv ) == true && cheie [ mat [ iv ] [ jv ] ] == 0 )
                lista.push_back({iv,jv });
        }

        q.pop();
    }
}
int main()
{
    long long x = 1, y;

    in >> n >> m >> y ;


    for ( int i = 1; i <= n ; i ++ )
    {
        for ( int j = 1; j <= m ; j ++ )
        {
            in >> mat[ i] [ j ] ;

            lem [ i ] [ j ] = x;
            mp [ x ] . first = i ;
            mp [ x ] . second = j ;
            x ++ ;
        }
    }

    cheie [ mat [mp [ y ] . first ] [ mp [ y ] .second ] ] = 1 ;

    int start = mp [ y ] .first ;
    int finish = mp [ y ]. second ;
    dist [ start ] [ finish ] = 1 ;
    q.push({start,finish});

    lee ();
    while ( conditie == true  )
    {
        conditie = false ;


        for ( int i = 0 ; i < lista.size() ; i ++ )
        {

            if ( dist [ lista [ i ] .first ] [ lista [ i ].second ] != 0  )
            {
                swap ( lista [ i ], lista [lista.size() - 1 ]);
                lista.pop_back();
                i -- ;
            }
            else if ( cheie [ mat[lista [ i  ] . first][lista [ i ] .second ]] != 0  )
            {
                q.push( {lista [ i ] . first, lista [ i ].second} ) ;
                conditie = true ;

                swap ( lista [ i ], lista [ lista.size() - 1 ]);
                lista.pop_back();
                i -- ;
            }
        }
        lee();


    }

    long long patrate = 0 ;  ;
    for ( int i = 1; i <= n ; i ++ )
    {
        for ( int j = 1 ; j <= m ; j ++)
            if ( dist [ i ] [ j ] != 0 )
                patrate ++ ;

    }

    out << patrate ;
    in.close();
    out.close();
    return 0;
}