Cod sursa(job #94399)

Utilizator stef2nStefan Istrate stef2n Data 22 octombrie 2007 22:08:56
Problema Barbar Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.28 kb
//#define DEBUG

#include <cstdio>
#include <list>
#ifdef DEBUG
#include <iostream>
#endif
using namespace std;

#define NMAX 1005
const short int dlin[]={-1,0,0,1};
const short int dcol[]={0,-1,1,0};

int M, N;
char table[NMAX][NMAX];
short int dist[NMAX][NMAX];
list < pair<short int, short int> > L;
bool used[NMAX][NMAX];

int Nheap;
pair <short int, short int> heap[NMAX*NMAX];
int pozheap[NMAX][NMAX];
short int sol[NMAX][NMAX];

void read_data()
{
	scanf("%d %d\n",&M,&N);
	for(int i=0; i<M; ++i)
		fgets(table[i],NMAX,stdin);
}

void Lee()
{
	L.clear();
	for(int i=0; i<M; ++i)
		for(int j=0; j<N; j++)
		{
			used[i][j]=false;
			if(table[i][j]=='D')
			{
				dist[i][j]=0;
				used[i][j]=true;
				L.push_back(make_pair(i,j));
			}
		}
	while(!L.empty())
	{
		for(int i=0; i<4; i++)
		{
			short int lin=L.front().first+dlin[i];
			short int col=L.front().second+dcol[i];
			if(lin>=0 && lin<M && col>=0 && col<N && !used[lin][col])
			{
				dist[lin][col]=dist[L.front().first][L.front().second]+1;
				used[lin][col]=true;
				L.push_back(make_pair(lin,col));
			}
		}
		L.pop_front();
	}
#ifdef DEBUG
	cerr<<"Distantele pana la dragoni:"<<endl;
	for(int i=0; i<M; i++)
	{
		for(int j=0; j<N; j++)
			cerr<<dist[i][j]<<" ";
		cerr<<endl;
	}
#endif
}

void scufunda(int poz)
{
	while(2*poz<=Nheap)
	{
		int p=poz;
		if(sol[heap[p].first][heap[p].second] < sol[heap[2*poz].first][heap[2*poz].second])
			p=2*poz;
		if(2*poz+1<=Nheap && sol[heap[p].first][heap[p].second] < sol[heap[2*poz+1].first][heap[2*poz+1].second])
			p=2*poz+1;
		if(p==poz)
			return;
		pozheap[heap[p].first][heap[p].second]=poz;
		pozheap[heap[poz].first][heap[poz].second]=p;
		pair <short int, short int> aux=heap[p];
		heap[p]=heap[poz];
		heap[poz]=aux;
		poz=p;
	}
}

void ridica(int poz)
{
	while(poz>1)
	{
		if(sol[heap[poz].first][heap[poz].second] > sol[heap[poz/2].first][heap[poz/2].second])
		{
			pozheap[heap[poz].first][heap[poz].second]=poz/2;
			pozheap[heap[poz/2].first][heap[poz/2].second]=poz;
			pair <short int, short int> aux=heap[poz];
			heap[poz]=heap[poz/2];
			heap[poz/2]=aux;
		}
		else
			return;
		poz>>=1;
	}
}

int Lee_heap()
{
	pair <int, int> start;
	for(int i=0; i<M; i++)
		for(int j=0; j<N; j++)
		{
			used[i][j]=false;
			if(table[i][j]=='I')
				start=make_pair(i,j);
		}
	used[start.first][start.second]=true;
	Nheap=1;
	heap[1]=start;
	pozheap[start.first][start.second]=1;
	sol[start.first][start.second]=dist[start.first][start.second];
	while(Nheap)
	{
		if(table[heap[1].first][heap[1].second]=='O')
			return sol[heap[1].first][heap[1].second];
		for(int i=0; i<4; i++)
		{
			short int lin=heap[1].first+dlin[i];
			short int col=heap[1].second+dcol[i];
			if(lin>=0 && lin<M && col>=0 && col<N && table[lin][col]!='*' && table[lin][col]!='D')
				if(!used[lin][col])
				{
					used[lin][col]=true;
					heap[++Nheap]=make_pair(lin,col);
					pozheap[lin][col]=Nheap;
					sol[lin][col]=min(sol[heap[1].first][heap[1].second],dist[lin][col]);
					ridica(Nheap);
				}
				else
				{
					sol[lin][col]=max(sol[lin][col],min(sol[heap[1].first][heap[1].second],dist[lin][col]));
					ridica(pozheap[lin][col]);
				}
		}
		heap[1]=heap[Nheap--];
		scufunda(1);
	}
	return -1;
}


int main()
{
	freopen("barbar.in","r",stdin);
	freopen("barbar.out","w",stdout);
	read_data();
	Lee();
	printf("%d\n",Lee_heap());
	return 0;
}