Pagini recente » Borderou de evaluare (job #1824864) | Borderou de evaluare (job #930334) | Cod sursa (job #2931093)
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("barbar.in");
ofstream fout("barbar.out");
int mat[1005][1005],dist[1005][1005],ver[1005][1005];
int di[]= {-1,0,1,0};
int dj[]= {0,1,0,-1};
int starti,startj,stopi,stopj;
queue<pair<int,int>>q;
int main()
{
int n,m;
fin>>n>>m;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
char c;
fin>>c;
if(c=='D')
{
ver[i][j]=1;
q.push(make_pair(i,j));
}
else if(c=='*')
{
mat[i][j]=1;
}
else if(c=='I')
{
starti=i;
startj=j;
}
else if(c=='O')
{
stopi=i;
stopj=j;
}
}
}
while(!q.empty())
{
int i=q.front().first,j=q.front().second;
for(int k=0; k<4; k++)
{
if(i+di[k]>=1&&i+di[k]<=n&&j+dj[k]>=1&&j+dj[k]<=m&&ver[i+di[k]][j+dj[k]]==0)
{
ver[i+di[k]][j+dj[k]]=1;
dist[i+di[k]][j+dj[k]]=dist[i][j]+1;
q.push(make_pair(i+di[k],j+dj[k]));
}
}
q.pop();
}
/*for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(mat[i][j]==1)
{
fout<<'X'<<" ";
}
else
{
fout<<dist[i][j]<<" ";
}
}
fout<<endl;
}*/
int st=0,dr=dist[starti][startj],mj;
while(st+1<dr)
{
for(int i=1; i<=n; i++)
{
for(int j=1; j<=m; j++)
{
ver[i][j]=0;
}
}
int mj=(st+dr)/2;
q.push(make_pair(starti,startj));
while(!q.empty())
{
int i=q.front().first,j=q.front().second;
for(int k=0; k<4; k++)
{
if(i+di[k]>=1&&i+di[k]<=n&&j+dj[k]>=1&&j+dj[k]<=m&&ver[i+di[k]][j+dj[k]]==0&&dist[i+di[k]][j+dj[k]]>=mj&&mat[i+di[k]][j+dj[k]]==0)
{
ver[i+di[k]][j+dj[k]]=1;
q.push(make_pair(i+di[k],j+dj[k]));
}
}
q.pop();
}
if(ver[stopi][stopj]==0)
{
dr=mj-1;
}
else
{
st=mj;
}
}
fout<<st;
return 0;
}