Pagini recente » Cod sursa (job #441558) | Cod sursa (job #211796)
Cod sursa(job #211796)
#include <iostream>
#include <stdio.h>
#include <string>
#include <queue>
using namespace std;
int n,m,x1,y1,x2,y2;
int a[175][175], r[175][175], ju[175][175],fin[175][175];
struct coord {int x,y;};
queue<coord> coada;
void citire()
{
char buffer[175];
string c;
freopen("rj.in","r",stdin);
scanf("%d %d",&n,&m);
gets(buffer);
for (int i=1; i<=n; i++)
{
gets(buffer);
c=buffer;
for (int j=0;j<c.length();j++)
{
if (c.substr(j,1)=="R")
{
a[i][j+1]=1;
x1=i;
y1=j+1;
}
if (c.substr(j,1)=="X")
a[i][j+1]=3;
if (c.substr(j,1)=="J")
{
a[i][j+1]=2;
x2=i;
y2=j+1;
}
}
}
}
void fill_matrice(int t[][175],int xstart,int ystart)
{
int auxx,auxy;
coord nod;
nod.x=xstart;
nod.y=ystart;
coada.push(nod);
t[xstart][ystart]=1;
while (!coada.empty())
{
auxx=coada.front().x;
auxy=coada.front().y;
coada.pop();
if (auxy-1>=1 && a[auxx][auxy-1]!=3 && t[auxx][auxy-1]==0)
{
t[auxx][auxy-1]=t[auxx][auxy]+1;
nod.x=auxx;
nod.y=auxy-1;
coada.push(nod);
}
if (auxy+1<=m && a[auxx][auxy+1]!=3 && t[auxx][auxy+1]==0)
{
t[auxx][auxy+1]=t[auxx][auxy]+1;
nod.x=auxx;
nod.y=auxy+1;
coada.push(nod);
}
if (auxx-1>=1 && a[auxx-1][auxy]!=3 && t[auxx-1][auxy]==0)
{
t[auxx-1][auxy]=t[auxx][auxy]+1;
nod.x=auxx-1;
nod.y=auxy;
coada.push(nod);
}
if (auxx+1<=n && a[auxx+1][auxy]!=3 && t[auxx+1][auxy]==0)
{
t[auxx+1][auxy]=t[auxx][auxy]+1;
nod.x=auxx+1;
nod.y=auxy;
coada.push(nod);
}
if (auxy-1>=1 && auxx-1>=1 && a[auxx-1][auxy-1]!=3 && t[auxx-1][auxy-1]==0)
{
t[auxx-1][auxy-1]=t[auxx][auxy]+1;
nod.x=auxx-1;
nod.y=auxy-1;
coada.push(nod);
}
if (auxy+1<=m && auxx-1>=1 && a[auxx-1][auxy+1]!=3 && t[auxx-1][auxy+1]==0)
{
t[auxx-1][auxy+1]=t[auxx][auxy]+1;
nod.x=auxx-1;
nod.y=auxy+1;
coada.push(nod);
}
if (auxy-1>=1 && auxx+1<=n && a[auxx+1][auxy-1]!=3 && t[auxx+1][auxy-1]==0)
{
t[auxx+1][auxy-1]=t[auxx][auxy]+1;
nod.x=auxx+1;
nod.y=auxy-1;
coada.push(nod);
}
if (auxy+1<=m && auxx+1<=n && a[auxx+1][auxy+1]!=3 && t[auxx+1][auxy+1]==0)
{
t[auxx+1][auxy+1]=t[auxx][auxy]+1;
nod.x=auxx+1;
nod.y=auxy+1;
coada.push(nod);
}
}
}
int main()
{
int min=0;
bool k=true;
citire();
fill_matrice(r,x1,y1);
fill_matrice(ju,x2,y2);
for (int i=1; i<=n;i++)
for (int j=1; j<=m;j++)
if (r[i][j]==ju[i][j] and r[i][j]>0)
{
fin[i][j]=r[i][j];
if (k)
{
min=r[i][j];
k=false;
}
if (r[i][j]<min)
min=r[i][j];
}
k=false;
for (int j=1; j<=m;j++)
{
for (int i=1; i<=n;i++)
if (fin[i][j]==min)
{
freopen ("rj.out","w",stdout);
printf ("%d %d %d",min,i,j);
fclose (stdout);
k=true;
break;
}
if (k) break;
}
return 0;
}