Cod sursa(job #673273)

Utilizator CrescentselectJicol Crescent Crescentselect Data 4 februarie 2012 11:09:57
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.58 kb
#include<iostream>
#include<fstream>
using namespace std;
int n,m;
int RomeoX,RomeoY,JulietaX,JulietaY;

void verifica_drum(int a, int b, int x, int y, short **cost, short **parinteX, short** parinteY, bool **vizitat)
{
	if(!vizitat[x][y])
		if(cost[x][y] !=-1)
		{
			int alt = cost[a][b]+1;
			if(alt < cost[x][y]) {
				cost[x][y] = alt;
				parinteX[x][y] = a;
				parinteY[x][y] = b;
			}
		}
}
int dist_min(int dist,short **cost, short **parinteX, short** parinteY, bool **vizitat)
{
	int i,j;
	while(1)
	{
		int pozX=-1,pozY=-1,min=10000;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				if(!vizitat[i][j] && cost[i][j]>=0 && cost[i][j]<min)
				{
					min=cost[i][j];
					pozX=i;
					pozY=j;
				}
			}
		}
		if(pozX==-1 || min==10000)
		{
			break;
		}
		vizitat[pozX][pozY]=true;
		
		for(i=-1;i<=1;i++)
		{
			for(j=-1;j<=1;j++)
			{
				if(i!=0 || j!=0)
					verifica_drum(pozX,pozY,pozX+i,pozY+j,cost,parinteX,parinteY,vizitat);
			}
		}
	}
	
	return cost[JulietaX][JulietaY];
}

int main()
{
	char linie[256];
	ifstream f("rj.in");
	ofstream g("rj.out");
	int i,j;
	f>>n;
	f>>m;
	f.getline(linie,256);
	
	short** cost;
	short** parinteX;
	short** parinteY;
	bool** vizitat;
	char mat[n+2][m+2];	
	
	cost = new short*[n+2];
	parinteX = new short*[n+2];
	parinteY = new short*[n+2];
	vizitat = new bool*[n+2];
	
	for(i=0;i<n+2;i++)
	{
		cost[i] = new short[m+2];
		parinteX[i] = new short[m+2];
		parinteY[i] = new short[m+2];
		vizitat[i] = new bool[m+2];
	}

	for(i=1;i<n+1;i++)
	{
		for(j=1;j<m+1;j++)
		{
			mat[i][j]=f.get();
			switch(mat[i][j])
			{
				case 'X':
					cost[i][j]=-1;
					break;
				case ' ':
					cost[i][j]=10000;
					break;
				case 'R':
					cost[i][j]=0;
					RomeoX=i;
					RomeoY=j;
					break;
				case 'J':
					cost[i][j]=10000;
					JulietaX=i;
					JulietaY=j;
					break;
			}
		}
		f.getline(linie,256);
	}
	
	for(i=0;i<n+2;i++)
	{
		cost[i][0]=-1;
		cost[i][n+1]=-1;
	}
	for(i=0;i<m+2;i++)
	{
		cost[0][i]=-1;
		cost[m+1][i]=-1;
	}
	
	for(i=0;i<n+2;i++)
		for(j=0;j<m+2;j++)
		{
			parinteX[i][j]=-1;
			parinteY[i][j]=-1;
			vizitat[i][j]=false;
		}
		
	int dist=dist_min(0,cost,parinteX,parinteY,vizitat);
	int tmp;
	if(dist%2==0)
	{
		tmp=dist/2;
	}
	else tmp=dist/2+1;
	
	int x = JulietaX;
	int y = JulietaY;
	
	for(i=0;i<tmp;i++)
	{
		if(parinteX[x][y] != -1) {
			int tmpX = parinteX[x][y];
			int tmpY = parinteY[x][y];
			x = tmpX;
			y = tmpY;
		}
	}
	g<<x<<" "<<y<<" ";
	g<<tmp;
	f.close();
	g.close();
	return 0;
}