Pagini recente » Borderou de evaluare (job #1289586) | Cod sursa (job #2541862)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("barbar.in");
ofstream fout("barbar.out");
int h[1002][1002];
int a[1002][1002];
//a[i][j] = maximul minimelor distantelor minime de la orice celula a unui drum la dragoni
queue <int> ql, qc;
int dl[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
void fill()
{
int la, ca, lv, cv, i;
while (ql.empty() == 0)
{
la = ql.front();
ca = qc.front();
ql.pop();
qc.pop();
for (i = 0; i<4; i++)
{
lv = la + dl[i];
cv = ca + dc[i];
if (h[lv][cv] == 0)
{
h[lv][cv] = h[la][ca] + 1;
ql.push(lv);
qc.push(cv);
}
}
}
}
int lee(int ls, int cs, int lf, int cf)
{
int la, ca, lv, cv, i;
int val;
a[ls][cs] = h[ls][cs];
ql.push(ls);
qc.push(cs);
while (ql.empty() == 0)
{
la = ql.front();
ca = qc.front();
ql.pop();
qc.pop();
for (i = 0; i<4; i++)
{
lv = la + dl[i];
cv = ca + dc[i];
if (h[lv][cv] > 0)
{
val = min(a[la][ca], h[lv][cv]);
if (a[lv][cv] == 0 || a[lv][cv] < val)
{
a[lv][cv] = val;
ql.push(lv);
qc.push(cv);
}
}
}
}
return a[lf][cf];
}
int main()
{
char buff[1002];
int i, j, n, m;
int ls, cs, lf, cf;
fin >> n >> m;
for (i = 1; i<=n; i++)
{
fin >> buff;
for (j = 1; j<=m; j++)
{
if (buff[j-1] == 'I')
{
ls = i;
cs = j;
}
else if (buff[j-1] == 'O')
{
lf = i;
cf = j;
}
else if (buff[j-1] == '*')
h[i][j] = -1;
else if (buff[j-1] == 'D')
{
h[i][j] = 1;
ql.push(i);
qc.push(j);
}
}
}
for (i = 0; i<=n+1; i++)
h[i][0] = h[i][m+1] = -1;
for (i = 0; i<=m+1; i++)
h[0][i] = h[n+1][i] = -1;
fill();
fout << lee(ls, cs, lf, cf) - 1;
return 0;
}