Pagini recente » Cod sursa (job #3261576) | Cod sursa (job #2892245) | Cod sursa (job #2504161) | Cod sursa (job #1681308) | Cod sursa (job #634332)
Cod sursa(job #634332)
#include<fstream>
#include<cstring>
#include<iostream>
using namespace std;
struct coord
{
short x,y;
};
coord q[200010];
short dx[] = {1, 1,1, 0,0,-1,-1,-1};
short dy[] = {0,-1,1,-1,1, 1, 0,-1};
int R[110][110],J[110][110];
int L,C,xR,yR,xJ,yJ;
void ReadData()
{
ifstream fin("rj.in");
fin>>L>>C;
fin.get();
int i,j;
char s[110];
for(i=1; i<=L; i++)
{
fin.getline(s,110);
for(j=0; j<C; j++)
if(s[j]==' ')
R[i][j+1] = 0;
else if(s[j]=='X')
R[i][j+1] = 1;
else if(s[j]=='R')
{
xR = i;
yR = j+1;
}
else
if(s[j]=='J')
{
xJ = i;
yJ = j+1;
}
}
fin.close();
for(i=1; i<=L; i++)
for(j=1; j<=C; j++)
J[i][j] = R[i][j];
//cout<<xR<<" "<<yR<<"\n";
//cout<<xJ<<" "<<yJ<<"\n";
}
void Bordare()
{
int i,n,m;
n = L + 1;
m = C + 1;
for(i=0; i<=n;i++)
R[i][0] = J[i][0] = R[i][m] = J[i][m] = -1;
for(i=0; i<=m; i++)
R[0][i] = J[0][i] = R[n][i] = J[n][i] = -1;
}
void Romeo()
{
int i,j,x,y,k,pr,ul;
pr = ul = 0;
R[xR][yR] = 1;
q[0].x = xR;
q[0].y = yR;
while(pr<=ul)
{
x = q[pr].x;
y = q[pr].y;
pr++;
for(k=0; k<8; k++)
{
i = x + dx[k];
j = y + dy[k];
if(R[i][j] == 0)
{
ul++;
q[ul].x = i;
q[ul].y = j;
R[i][j] = R[x][y] + 1;
}
}
}
}
void Julieta()
{
int i,j,x,y,k,pr,ul;
pr = ul = 0;
J[xJ][yJ] = 1;
q[0].x = xJ;
q[0].y = yJ;
while(pr<=ul)
{
x = q[pr].x;
y = q[pr].y;
pr++;
for(k=0; k<8; k++)
{
i = x + dx[k];
j = y + dy[k];
if(J[i][j] == 0)
{
ul++;
q[ul].x = i;
q[ul].y = j;
J[i][j] = J[x][y] + 1;
}
}
}
}
void Scriere()
{
int i,j,lin,col,timp = 1000000;
lin = col = 0;
for(i=1; i<=L; i++)
for(j=1; j<=C; j++)
{
if(R[i][j] == J[i][j] && R[i][j] > 1)
if(R[i][j] < timp)
{
lin = i;
col = j;
timp = R[i][j];
}
}
ofstream fout("rj.out");
fout<<timp<<" "<<lin<<" "<<col<<"\n";
fout.close();
}
int main ()
{
ReadData();
Bordare();
/*
ofstream fout("rj.out");
int i,j;
for(i=1; i<=L; i++)
{
for(j=1; j<=C; j++)
fout<<R[i][j]<<" ";
fout<<"\n";
}
fout.close();
*/
Romeo();
Julieta();
Scriere();
return 0;
}