Pagini recente » Istoria paginii utilizator/wordmeister | Monitorul de evaluare | Istoria paginii utilizator/popescovicescov | Autentificare | Cod sursa (job #2510195)
#include <fstream>
#include <queue>
const int NMAX = 101;
int A[NMAX+5][NMAX+5];
int B[NMAX+5][NMAX+5];
struct POINT
{
int x,y;
};
std::queue<POINT> q;
int dx[] = {-1,-1, 0, 1, 1, 1,0,-1};
int dy[] = { 0, 1, 1, 1, 0, -1,-1,-1};
POINT startRomeo,startJulieta;
int m,n;
std::ifstream fin("rj.in");
std::ofstream fout("rj.out");
void leeA()
{
int i;
POINT fr,nou;
q.push(startRomeo);
A[startRomeo.x][startRomeo.y] = 1;
while(!q.empty())
{
fr = q.front();
q.pop();
for(i=0; i<8; i++)
{
nou.x = fr.x + dx[i];
nou.y = fr.y + dy[i];
if(A[nou.x][nou.y]==0)
{
q.push(nou);
A[nou.x][nou.y] = A[fr.x][fr.y] + 1;
}
}
}
}
void leeB()
{
while(!q.empty()) q.pop();
int i;
POINT fr,nou;
q.push(startJulieta);
B[startJulieta.x][startJulieta.y] = 1;
while(!q.empty())
{
fr = q.front();
q.pop();
for(i=0; i<8; i++)
{
nou.x = fr.x + dx[i];
nou.y = fr.y + dy[i];
if(B[nou.x][nou.y]==0)
{
q.push(nou);
B[nou.x][nou.y] = B[fr.x][fr.y] + 1;
}
}
}
}
int main()
{
int i,j;
char ch;
fin>>n>>m;
fin.get(); //enter char
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
ch = fin.get();
if(ch=='X') //obstacol
{
A[i][j] = -1;
B[i][j] = -1;
}
if(ch=='R') //start Romeo
{
startRomeo.x= i;
startRomeo.y = j;
}
if(ch=='J') //start Julieta
{
startJulieta.x = i;
startJulieta.y = j;
}
}
fin.get(); //enter char
}
//bordare
for(j=0; j<=m+1; j++)
{
A[0][j] = A[n+1][j] = -1;
B[0][j] = B[n+1][j] = -1;
}
for(i=0; i<=n+1; i++)
{
A[i][0] = A[i][m+1] = -1;
B[i][0] = B[i][m+1] = -1;
}
leeA();
leeB();
int minim = 999999;
POINT pozMin;
for(i=1; i<=n; i++)
{
for(j=1; j<=m; j++)
{
if(A[i][j] == B[i][j] && A[i][j]!=-1 && A[i][j]!=0)
if(A[i][j]<minim)
{
minim = A[i][j];
pozMin.x = i;
pozMin.y = j;
}
}
}
fout<<minim<<" "<<pozMin.x<<" "<<pozMin.y;
return 0;
}