Pagini recente » Cod sursa (job #487493) | Cod sursa (job #2814485) | Cod sursa (job #1980565) | Cod sursa (job #2986542) | Cod sursa (job #2990991)
#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;
}