Pagini recente » Cod sursa (job #1318357) | Cod sursa (job #2655411) | Cod sursa (job #1329995) | Cod sursa (job #716374) | Cod sursa (job #2113879)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
using namespace std;
struct node
{
int x,y,val,distR, distJ;
};
const int mutX[] = {-1, -1, 0, 1, 1, 1, 0, -1};
const int mutY[] = {0, 1, 1, 1, 0, -1, -1, -1};
//N, N-E, E, S-E, S, S-W, W, N-W
/*
Legenda:
-1 = bordura
1 = drum deschis
0 = perete
2 = start romeo
3 = start julieta
*/
queue<node> coada;
node Julieta, intersectie;
int main()
{
ifstream f ("rj.in");
ofstream g ("rj.out");
int n,m;
node mat[101][101];
f>>n>>m;
f.get();
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
mat[i][j].x=i;
mat[i][j].y=j;
char x;
bool citit = false;
while(!citit)
{
f.get(x);
if(x=='X') {mat[i][j].val = 0; citit=true;}
else if (x==' ') { mat[i][j].val = 1; mat[i][j].distR = -1; mat[i][j].distJ = -1; citit=true;}
else if (x=='R') { mat[i][j].val = 2; mat[i][j].distR = 0; coada.push(mat[i][j]); citit=true; }
else if (x=='J') { mat[i][j].val = 3; mat[i][j].distJ = 0; Julieta = mat[i][j]; citit=true; }
}
}
}
//bordare matrice
node bordura;
bordura.val = -1;
bordura.x=-1;
bordura.y=-1;
for(int i=0;i<=n+1;i++)
for(int j=0;j<=m;j++)
{
mat[i][0] = bordura;
mat[i][m+1] = bordura;
mat[0][j] = bordura;
mat[n+1][j] = bordura;
}
//lee de la Romeo pe toata matricea
while(!coada.empty())
{
node currentPos = coada.front();
coada.pop();
for(int i=0;i<=7;i++)
{
node nextPos = currentPos;
nextPos.x+=mutX[i];
nextPos.y+=mutY[i];
nextPos.distR++;
if(mat[nextPos.x][nextPos.y].val==1 && mat[nextPos.x][nextPos.y].distR==-1)
{
mat[nextPos.x][nextPos.y].distR = nextPos.distR;
coada.push(nextPos);
}
}
}
//lee Julieta
coada.push(Julieta);
bool found = false;
while(!coada.empty() & !found)
{
node currentPos = coada.front();
coada.pop();
for(int i=0;i<=7;i++)
{
node nextPos = currentPos;
nextPos.x+=mutX[i];
nextPos.y+=mutY[i];
nextPos.distJ++;
if(mat[nextPos.x][nextPos.y].val==1 && mat[nextPos.x][nextPos.y].distJ == -1)
{
mat[nextPos.x][nextPos.y].distJ = nextPos.distJ;
coada.push(nextPos);
if(mat[nextPos.x][nextPos.y].distJ == mat[nextPos.x][nextPos.y].distR)
{
found = true;
intersectie = mat[nextPos.x][nextPos.y];
}
}
}
}
g<<intersectie.distR<<" "<<intersectie.x<<" "<<intersectie.y<<'\n';
f.close();
g.close();
return 0;
}