Pagini recente » Cod sursa (job #1240112) | Cod sursa (job #2807712) | Cod sursa (job #1617654) | Cod sursa (job #452542) | Cod sursa (job #1169866)
#include <fstream>
using namespace std;
char a[103][103];
int b[103][103],c[103][103], m, n,k,xr,yr,xj,yj,ii,jj,minim;
struct coord
{
int x, y, c;
};
coord q[10009],p[10009];
int dx[] = {-1, 0, 1, 0, -1,1,-1,1};
int dy[] = { 0, 1, 0, -1, -1,1,1,-1};
void Citire()
{
ifstream fin("rj.in");
fin >> n >> m;
fin.get();
for (int i = 1; i <= n; i++)
fin.getline((a[i] + 1), 101);
fin.close();
}
void Bordare()
{
int i,j;
for(i = 0;i<=n+1;i++)
a[i][0] = a[i][m+1] = 'X';
for(i = 0;i<=m+1;i++)
a[0][i] = a[n+1][i] = 'X';
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if (a[i][j] == 'R') {xr=i; yr=j;}
if (a[i][j] == 'J') {xj=i; yj=j;}
}
}
}
void Afisare()
{ int i,j;
ofstream fout("rj.out");
fout<<minim<<" "<<ii<<" "<<jj<<"\n";
}
void Inserare(coord w)
{
int i;
i = k;
while (i >= 0 && q[i].c < w.c)
{
q[i+1] = q[i];
i--;
}
q[i+1] = w;
k++;
}
void Lee1()
{
int j;
coord w, w1;
q[0].x = xr;
q[0].y = yr;
q[0].c = 1;
b[xr][yr] = 1;
k = 0;
while (k >= 0)
{
w = q[k];
k--;
for (j = 0; j < 8; j++)
{
w1.x = w.x + dx[j];
w1.y = w.y + dy[j];
if ( (a[w1.x][w1.y] == ' ' || a[w1.x][w1.y] == 'R'|| a[w1.x][w1.y] == 'J' ) && (b[w1.x][w1.y] == 0 || b[w1.x][w1.y] > b[w.x][w.y] + 1) )
{
w1.c = b[w1.x][w1.y] = b[w.x][w.y] + 1;
Inserare(w1);
}
}
}
}
void Lee2()
{
int j,i;
coord w, w1;
for(i=0;i<10003;i++)
q[i].x = q[i].y = q[i].c=0;
q[0].x = xj;
q[0].y = yj;
q[0].c = 1;
c[xj][yj] = 1;
k = 0;
while (k >= 0)
{
w = q[k];
k--;
for (j = 0; j < 8; j++)
{
w1.x = w.x + dx[j];
w1.y = w.y + dy[j];
if ( (a[w1.x][w1.y] == ' ' || a[w1.x][w1.y] == 'R'|| a[w1.x][w1.y] == 'J' ) && (c[w1.x][w1.y] == 0 || c[w1.x][w1.y] > c[w.x][w.y] + 1) )
{
w1.c = c[w1.x][w1.y] = c[w.x][w.y] + 1;
Inserare(w1);
}
}
}
}
void Done()
{ int i,j;
minim = 999999999;
for(i = 1;i<=n;i++)
for(j = 1;j<=m;j++)
if(b[i][j] == c[i][j] && b[i][j]<minim&&b[i][j] != 0) {minim = b[i][j]; ii = i;jj=j;}
}
int main()
{
Citire();
Bordare();
Lee1();
Lee2();
Done();
Afisare();
return 0;
}