Pagini recente » Istoria paginii runda/testround7 | Cod sursa (job #1710798)
#include <fstream>
#include <cstring>
using namespace std;
ifstream y("rj.in");
ofstream w("rj.out");
int main()
{
int m,n,x1,y1,x2,y2,X,Y,P,l,cc,b[100][100],c[100][100],d[100][100],s,f;
char a[100][100];
y>>n>>m;
struct {
int x,y,p;
}Q[10001];
char str[101];
y.getline(str,100);
for (int i = 1; i <= n; i++)
{
y.getline(str,100);
for (int j = 0; j < strlen(str); j++)
{
if (str[j] == ' ')
b[i][j+1] = 999,c[i][j+1]=999;
else if (str[j] == 'X')
b[i][j+1] = -1,c[i][j+1]=-1;
else
if (str[j]=='R')
x1=i,y1=j+1;
else if(str[j]=='J')
x2=i,y2=j+1,b[i][j+1]=999,c[i][j+1]=999;
}
if (strlen(str) < m)
for (int j = strlen(str)+1; j <=m; j++)
b[i][j] = 999,c[i][j]=999;
}
//ROMEO
Q[1].x=x1;
Q[1].y=y1;
Q[1].p=0;
s=1;f=2;
for(int p=1;p<=n;p++)
for(int r=1;r<=m;r++)
d[p][r]=0;
while(s<=f)
{
X=Q[s].x;
Y=Q[s].y;
P=Q[s].p;
if(b[X-1][Y]==999 && !d[X-1][Y])
{
Q[f].x=X-1;
Q[f].y=Y;
Q[f].p=P+1;
d[X-1][Y]=1;
f++;
}
if(b[X+1][Y]==999 && !d[X+1][Y])
{
Q[f].x=X+1;
Q[f].y=Y;
Q[f].p=P+1;
d[X-1][Y]=1;
f++;
}
if(b[X][Y-1]==999 && !d[X][Y-1])
{
Q[f].x=X;
Q[f].y=Y-1;
Q[f].p=P+1;
d[X][Y-1]=1;
f++;
}
if(b[X][Y+1]==999 && !d[X][Y+1])
{
Q[f].x=X;
Q[f].y=Y+1;
Q[f].p=P+1;
d[X][Y+1]=1;
f++;
}
if(b[X+1][Y+1]==999 && !d[X+1][Y+1])
{
Q[f].x=X+1;
Q[f].y=Y+1;
Q[f].p=P+1;
d[X+1][Y+1]=1;
f++;
}
if(b[X-1][Y-1]==999 && !d[X-1][Y-1])
{
Q[f].x=X-1;
Q[f].y=Y-1;
Q[f].p=P+1;
d[X-1][Y-1]=1;
f++;
}
if(b[X+1][Y-1]==999 && !d[X+1][Y-1])
{
Q[f].x=X+1;
Q[f].y=Y-1;
Q[f].p=P+1;
d[X+1][Y-1]=1;
f++;
}
if(b[X-1][Y+1]==999 && !d[X-1][Y+1])
{
Q[f].x=X-1;
Q[f].y=Y+1;
Q[f].p=P+1;
d[X-1][Y+1]=1;
f++;
}
s++;
}
for(int i=2; i<f; i++)
{
if(Q[i].p < b[ Q[i].x ] [ Q[i].y ]) b[Q[i].x][Q[i].y]=Q[i].p;
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++)
{
if(a[i][j]==' ') b[i][j]=999;else
if(a[i][j]=='X') b[i][j]=-1;
}
// JULIETA
Q[1].x=x2;
Q[1].y=y2;
Q[1].p=0;
s=1;f=2;
for(int p=1;p<=n;p++)
for(int r=1;r<=m;r++)
d[p][r]=0;
while(s<=f)
{
X=Q[s].x;
Y=Q[s].y;
P=Q[s].p;
if(c[X-1][Y]==999 && !d[X-1][Y])
{
Q[f].x=X-1;
Q[f].y=Y;
Q[f].p=P+1;
d[X-1][Y]=1;
f++;
}
if(c[X+1][Y]==999 && !d[X+1][Y])
{
Q[f].x=X+1;
Q[f].y=Y;
Q[f].p=P+1;
d[X+1][Y]=1;
f++;
}
if(c[X][Y-1]==999 && !d[X][Y-1])
{
Q[f].x=X;
Q[f].y=Y-1;
Q[f].p=P+1;
d[X][Y-1]=1;
f++;
}
if(c[X][Y+1]==999 && !d[X][Y+1])
{
Q[f].x=X;
Q[f].y=Y+1;
Q[f].p=P+1;
d[X][Y+1]=1;
f++;
}
if(c[X+1][Y+1]==999 && !d[X+1][Y+1])
{
Q[f].x=X+1;
Q[f].y=Y+1;
Q[f].p=P+1;
d[X+1][Y+1]=1;
f++;
}
if(c[X-1][Y-1]==999 && !d[X-1][Y-1])
{
Q[f].x=X-1;
Q[f].y=Y-1;
Q[f].p=P+1;
d[X-1][Y-1]=1;
f++;
}
if(c[X+1][Y-1]==999 && !d[X+1][Y-1])
{
Q[f].x=X+1;
Q[f].y=Y-1;
Q[f].p=P+1;
d[X+1][Y-1]=1;
f++;
}
if(c[X-1][Y+1]==999 && !d[X-1][Y+1])
{
Q[f].x=X-1;
Q[f].y=Y+1;
Q[f].p=P+1;
d[X-1][Y+1]=1;
f++;
}
s++;
}
int mini=999999;
for(int i=2; i<f; i++)
if(Q[i].p < c[ Q[i].x ] [ Q[i].y ]) c[Q[i].x][Q[i].y]=Q[i].p;
for(int i=2; i<f; i++)
if(b[Q[i].x][Q[i].y]==c[Q[i].x][Q[i].y])
if(Q[i].p<mini)
{
mini=Q[i].p;
l=Q[i].x;
cc=Q[i].y;
}
mini++;
w<< mini <<' '<<l<<' '<<cc;
return 0;
}