Pagini recente » Cod sursa (job #2529017) | Cod sursa (job #1804901) | Cod sursa (job #2776486) | Cod sursa (job #1827004) | Cod sursa (job #673273)
Cod sursa(job #673273)
#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;
}