Pagini recente » Cod sursa (job #1028808) | Cod sursa (job #1067933) | Cod sursa (job #448353) | Cod sursa (job #711693) | Cod sursa (job #1520722)
/// 0p pe infoarena, 4 teste OK. Algoritmul e bun, ramase doar chichite pt solutia buna
#include <iostream>
#include <string.h>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream g("rj.out");
struct coord {int x, y;};
coord s, f, rr, jj;
int R[105][105], J[105][105], n, m, i, j;
const int dx[8]={-1,-1,0,1,1,1,0,-1}, dy[8]={0,1,1,1,0,-1,-1,-1};
queue<coord> c;
char ch[105];
void Lee(int d[][105], coord s)
{ d[s.x][s.y]=1;
c.push(s);
while (!c.empty())
{ coord a=c.front();
c.pop();
for(int k=0;k<8;k++)
{ coord aa;
aa.x=a.x+dx[k];
aa.y=a.y+dy[k];
if(aa.x>0 && aa.y>0 && aa.x<=n && aa.y<=n && d[aa.x][aa.y]==0)
{ d[aa.x][aa.y]=d[a.x][a.y]+1;
c.push(aa);
}
}
}
}
int main()
{ fin>>n>>m;
for(i=0;i<=n;i++)
{ fin.getline(ch,105);
for(j=0;j<strlen(ch);j++)
{ if (ch[j]=='R')//retinem locatia lui Romeo
{ rr.x=i;
rr.y=j+1;
}
if (ch[j]=='J')//retinem locatia lui Julieta
{ jj.x=i;
jj.y=j+1;
}
if (ch[j]=='X')//marcam obstacolele in ambele matrici
{ R[i][j+1]=-1;
J[i][j+1]=-1;
}
}
}
//algoritmul lui Lee pt matricea lui R si J
Lee(R, rr);
Lee(J, jj);
/*for(i=1;i<=n;i++)
{ for(j=1;j<=m;j++)
cout<<R[i][j]<<' ';
cout<<endl;
}
cout<<endl;
for(i=1;i<=n;i++)
{ for(j=1;j<=m;j++)
cout<<J[i][j]<<' ';
cout<<endl;
}*/
int minn=1<<30,ii,jj;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if (R[i][j]==J[i][j] && R[i][j]>0 ) //daca e punct comun si nu e obstacol
{ if (R[i][j]<minn)
{ minn=R[i][j];
ii=i; jj=j;
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(R[i][j]==minn && j>jj) jj=j;
g<<minn<<' '<<ii<<' '<<jj<<' ';
return 0;
}