Pagini recente » Cod sursa (job #3268709) | Cod sursa (job #2642636) | Cod sursa (job #2860137) | Cod sursa (job #2706333) | Cod sursa (job #1399365)
#include<cstdio>
#include<algorithm>
#include<deque>
using namespace std;
deque<pair<int,int> > cd, cd2;
const int dx[4]={0, 1, 0, -1};
const int dy[4]={1, 0, -1, 0};
pair<int,int> p;
int i, j, n, m, x, y, a[1002][1002], b[1002][1002], x1, x2, y1, y2, st, dr, mij, k, sol;
char s[1002];
bool test(int dist){
int k; ///
for (i=1;i<=n;i++) for (j=1;j<=m;j++)
if (a[i][j]>=dist) b[i][j]=999999999; else b[i][j]=-1;
cd.clear(); cd.push_back(make_pair(x1,y1)); b[x1][y1]=0;
while (!cd.empty()) {
if (b[x2][y2]!=999999999) return true;
p=cd.front(); x=p.first; y=p.second; cd.pop_front();
for (k=0;k<=3;k++) if (b[x+dx[k]][y+dy[k]]>=b[x][y]+1) {
b[x+dx[k]][y+dy[k]]=b[x][y]+1;
cd.push_back(make_pair(x+dx[k], y+dy[k]));
}
}
if (b[x2][y2]!=999999999) return true; else return false;
}
int main(){
freopen("barbar.in","r",stdin);
freopen("barbar.out","w",stdout);
scanf("%d%d\n", &n, &m);
for (i=1;i<=n;i++) {a[i][0]=-1; a[i][m+1]=-1; b[i][0]=-1; b[i][m+1]=-1;}
for (i=1;i<=m;i++) {a[0][i]=-1; a[n+1][i]=-1; b[0][i]=-1; b[n+1][i]=-1;}
for (i=1;i<=n;i++) {
gets(s); for (j=0;j<m;j++) {
if (s[j]=='.') a[i][j+1]=999999999;
if (s[j]=='*') a[i][j+1]=-1;
if (s[j]=='D') {a[i][j+1]=0; cd.push_back(make_pair(i,j+1));}
if (s[j]=='I') {a[i][j+1]=999999999; x1=i; y1=j+1;}
if (s[j]=='O') {a[i][j+1]=999999999; x2=i; y2=j+1;}
}
} dr=0;
while (!cd.empty()) {
dr++;
while (!cd.empty()) {
p=cd.front(); x=p.first; y=p.second; cd.pop_front();
for (k=0;k<=3;k++) if (a[x+dx[k]][y+dy[k]]>a[x][y]+1) {
a[x+dx[k]][y+dy[k]]=a[x][y]+1;
cd2.push_back(make_pair(x+dx[k], y+dy[k]));
}
} cd2.swap(cd); cd2.clear();
}
if (a[x1][y1]<a[x2][y2]) st=dr-a[x2][y2]; else st=dr-a[x1][y1]; sol=-1;
for (mij=st+(dr-st)/2;st<dr;mij=st+(dr-st)/2) {
if (test(mij)==true) {sol=mij; st=mij+1;}
else dr=mij-1;
}
if (test(st)==true) sol=st;
printf("%d\n", sol); return 0;
}