Pagini recente » Cod sursa (job #2667782) | Cod sursa (job #3282681) | Cod sursa (job #2623985) | Cod sursa (job #2258395) | Cod sursa (job #2666033)
#include <iostream>
#include <queue>
#include <string>
#include <fstream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
///pentru a schimba pozitia pionului, relativ la pozitia sa initiala
int dx[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
int dy[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
int matrixr[101][101];
int matrixj[101][101];
int n,m;
struct cell
{
int x,y;
cell(int x = 0, int y = 0):x(x),y(y) {}
};
queue<cell> c1;
queue<cell> c2;
int in(int x, int y)
{
if(x >= 0 && x < n && y >=0 && y < m)
return 1;
return 0;
}
void leer()
{
while(!c1.empty())
{
cell parent = c1.front();
for(int i = 0; i < 8; i++)
{
int x = parent.x + dx[i];
int y = parent.y + dy[i];
if(in(x,y) == 1 && matrixr[x][y] == 0)
{
matrixr[x][y] = matrixr[parent.x][parent.y] + 1;
c1.push(cell(x,y));
}
}
c1.pop();
}
}
void leej()
{
while(!c2.empty())
{
cell parent = c2.front();
for(int i = 0; i < 8; i++)
{
int x = parent.x + dx[i];
int y = parent.y + dy[i];
if(in(x,y) == 1 && matrixj[x][y] == 0)
{
matrixj[x][y] = matrixj[parent.x][parent.y] + 1;
c2.push(cell(x,y));
}
}
c2.pop();
}
}
int main()
{
cell start;
cell finish;
///citim datele
fin>>n>>m;
fin.get();
for(int i=0; i<n; i++)
{
string str;
getline(fin,str);
for(int j = 0; j < str.length(); j ++)
{
if(str[j] == 'R')
{
start.x = i;
start.y = j;
}
else if(str[j] == 'J')
{
finish.x = i;
finish.y = j;
}
else if(str[j] == 'X')
{
matrixr[i][j] = -1;
matrixj[i][j] = -1;
}
}
}
///housekeeping stuff
c1.push(start);
c2.push(finish);
matrixr[start.x][start.y] = 1;
matrixj[finish.x][finish.y] = 1;
///apelam 2 lee-uri: unul pentru julieta si unul pentru romeo
leer();
leej();
///cautam drumul minim
int minim = 100000,x,y;
for(int i = 0; i < n; i ++ )
for(int j = 0; j < m; j ++ )
{
if (matrixr[i][j] == matrixj[i][j] && matrixj[i][j] < minim && matrixr[i][j] > 0)
{
minim = matrixj[i][j];
x = i;
y = j;
}
}
fout<<minim <<" "<< x + 1 << " " << y + 1;
return 0;
}