Pagini recente » Cod sursa (job #104497) | Cod sursa (job #134586)
Cod sursa(job #134586)
#include <fstream>
#include <string.h>
#define MAX 1105
using namespace std;
ifstream fin ("barbar.in");
ofstream fout ("barbar.out");
const int x[4]={-1,0,0,1};
const int y[4]={0,-1,1,0};
int a[MAX][MAX],n,m,xi,xf,yf,yi,ii[3000001],jj[3000001],numar,ok=0,minim,b[MAX][MAX];
void citire()
{
char s[1010];
fin>>n>>m;
fin.getline(s,1030);
for (int i=1;i<=n;i++)
{
fin.getline(s,1010);
for (int j=0;j<=m;j++)
if (s[j]=='*')
a[i][j+1]=-1;
else
if (s[j]=='D')
{
ii[numar]=i;
jj[numar]=j+1;
a[i][j+1]=1;
numar++;
}
else
if (s[j]=='I')
{
xi=i;
yi=j+1;
}
else
if (s[j]=='O')
{
xf=i;
yf=j+1;
}
}
}
int min (int a,int b)
{
if (a<b)
return a;
return b;
}
void lee ()
{
int nr=numar;
for (int i=0;i<nr;i++)
for (int k=0;k<4;k++)
if (a[ii[i] +x[k]][jj[i] +y[k]]==0 ){
a[ii[i] +x[k]][jj[i] +y[k]] = a[ii[i]][jj[i]]+1;
ii[nr]=ii[i]+x[k];
jj[nr]=jj[i]+y[k];
nr++;
}
}
void fct()
{
int max=n;
if (m>n)
max=m;
for (int r=0;r<=max;r++)
{
a[r][0]=-1;
a[r][m+1]=-1;
a[n+1][r]=-1;
a[0][r]=-1;
}
lee();
}
int da(int ups)
{
memset(b,0,sizeof(b));
ii[0]=xi;
jj[0]=yi;
int nr=0;
if (a[xi][yi]>=ups){
b[xi][yi]=1;
nr=1;
}
for ( int i=0;i<nr;i++)
for ( int k=0;k<4;k++)
if (a[ii[i] +x[k]][jj[i] +y[k]]>=ups&& b[ii[i]+x[k]][jj[i]+y[k]]==0)
{
b[ii[i] +x[k]][jj[i] +y[k]]=1;
ii[nr]=ii[i]+x[k];
jj[nr]=jj[i]+y[k];
nr++;
}
return b[xf][yf];
}
void caut()
{
int max=-1;
for (int q=1;q<=n;q++)
for (int w=1;w<=m;w++)
if (a[q][w]>max)
max=a[q][w];
minim=max;
for (int v=max;v>=-1;v--)
if (da(v))
{
minim=v;
return;
}
}
int main ()
{
minim=0;
citire();
fct();
caut();
// if (a[xf][yf]==0)
// fout<<"-1\n";
// else{
// if (minim>0)
fout<<minim-1<<"\n";
// else
// fout<<"-1\n";
}
fout.close();
return 0;
}