Pagini recente » Cod sursa (job #709861) | Cod sursa (job #240696) | Cod sursa (job #1986535) | Cod sursa (job #2549732) | Cod sursa (job #1054832)
#include <fstream>
#include <iomanip>
#include <vector>
#include <queue>
using namespace std;
ifstream is("barbar.in");
ofstream os("barbar.out");
const int INF = 0x3f3f3f3f;
const int di[] = { -1, 0, 1, 0 },
dj[] = { 0, 1, 0, -1 };
int m, n, i1, j1, i2, j2, dmax, iv, jv, i, j;
int d[1001][1001];
char a[1001][1001];
queue<pair< int, int> > Q;
void Read();
void Lee();
bool Ok ( int i, int j );
void Write();
bool Check( int x );
void Solve();
int main()
{
Read();
Lee();
//Write();
Solve();
is.close();
os.close();
return 0;
}
void Solve()
{
for ( int i = d[i1][j1]; i >= 1; i--)
if ( Check(i) == true)
{
os << i;
return;
}
os << -1;
}
bool Check( int x )
{
deque<pair<int, int> > q;
vector<vector<bool> > ver ( m + 1, vector<bool>( n + 1, false));
int i = i1, j = j1;
q.push_back(make_pair(i, j) );
ver[i1][j1] = true;
while ( !q.empty() )
{
i = q.front().first, j = q.front().second;
q.pop_front();
for ( int k = 0; k < 4; k++ )
{
iv = i + di[k], jv = j + dj[k];
if ( Ok(iv, jv ) && ver[iv][jv] == false && d[iv][jv] >= x )
{
ver[iv][jv] = true, q.push_back(make_pair(iv, jv));
if ( iv == i2 && jv == j2 )
return true;
}
}
}
return false;
}
void Lee()
{
while ( !Q.empty() )
{
i = Q.front().first;
j = Q.front().second;
Q.pop();
for ( int k = 0; k < 4; k++ )
{
iv = i + di[k], jv = j + dj[k];
if ( Ok( iv, jv ) && d[iv][jv] == 0 )
{
d[iv][jv] = d[i][j] + 1;
dmax = max(dmax, d[iv][jv]);
Q.push(make_pair(iv, jv ));
}
}
}
}
bool Ok( int i, int j )
{
if ( i < 1 || j < 1 || i > m || j > n )
return false;
if ( a[i][j] == '*' || a[i][j] == 'D' )
return false;
return true;
}
void Read()
{
is >> m >> n;
for ( int i = 1; i <= m; i++ )
for ( int j = 1; j <= n; j++ )
{
is >> a[i][j];
if ( a[i][j] == 'I' )
i1 = i, j1 = j;
if ( a[i][j] == 'O' )
i2 = i, j2 = j;
if ( a[i][j] == 'D' )
Q.push(make_pair(i,j));
}
}
void Write()
{
for ( int i = 1; i <= m; i++ )
{
for ( int j = 1; j <= n; j++ )
os << d[i][j] << ' ';
os << '\n';
}
}