Pagini recente » Cod sursa (job #2191736) | Cod sursa (job #306001) | Cod sursa (job #37092) | Cod sursa (job #3218914) | Cod sursa (job #2671864)
#include <fstream>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
short v[101][101], m, n, i, j, xj[10009], yj[10009], xr[10009], yr[10009];
short dx[]= {-1,-1,-1,0,0,1,1,1}, dy[]= {-1,0,1,-1,1,-1,0,1}, p, u, k, small = 32000;
bool viz1[101][101], viz2[101][101];
char s[101];
short mim1[101][101], mim2[101][101], xs, ys;
bool inside(int x, int y)
{
return x <= n && y <= m && x => 1 && y => 1; //daca e in matrice
}
void lee1()
{
u = 1;
p = 0;
viz1[xr[1]][yr[1]] = 1; //exact ca un dfs
while(p <= u)
{
++p;
for(k = 0; k < 8; ++k)
{
if(inside(xr[p] + dx[k], yr[p] + dy[k]))
{
if(!viz1[xr[p] + dx[k]][yr[p] + dy[k]])
{
if(!v[xr[p] + dx[k]][yr[p] + dy[k]])
{
++u;
xr[u] = xr[p] + dx[k]; //vecinul
yr[u]=yr[p] + dy[k];
viz1[xr[u]][yr[u]] = 1; //il vizitez si pe el
mim1[xr[u]][yr[u]] = mim1[xr[p]][yr[p]] + 1; //calculez drumul
}
}
}
}
}
}
void lee2()
{
u = 1;
p = 0;
viz2[xj[1]][yj[1]] = 1;
while(p<=u)
{
++p;
for(k = 0; k < 8; ++k)
{
if(inside(xj[p] + dx[k], yj[p] + dy[k]))
{
if(!viz2[xj[p] + dx[k]][yj[p] + dy[k]])
{
if(!v[xj[p] + dx[k]][yj[p] + dy[k]])
{
++u;
xj[u] = xj[p] + dx[k];
yj[u] = yj[p] + dy[k];
viz2[xj[u]][yj[u]] = 1;
mim2[xj[u]][yj[u]] = mim2[xj[p]][yj[p]] + 1;
}
}
}
}
}
}
int main()
{
f >> n >> m;
f.get();
for(i = 1; i <= n; ++i)
{
f.getline(s + 1, 110);
for(j = 1; j <= m; ++j)
{
if(s[j] == 'R')
{
xr[1] = i;
yr[1] = j;
}
if(s[j] == 'J')
{
xj[1] = i;
yj[1] = j;
}
if(s[j] == 'X')
v[i][j] = 1;
}
}
lee1();
lee2();
for(i = 1; i <= n; ++i)
{
for(j = 1; j <= m; ++j)
{
if(mim1[i][j] == mim2[i][j] && mim1[i][j] < small && mim1[i][j])
{
xs = i; //pozitia de intalnire
ys = j;
small = mim1[i][j]; //meet in the middle
}
}
}
g<<small+1<<' '<<xs<<' '<<ys;
return 0;
}