Pagini recente » Cod sursa (job #1181555) | Cod sursa (job #34994) | Cod sursa (job #38171) | Cod sursa (job #1181542) | Cod sursa (job #1096553)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
const int NMAX = 102;
using namespace std;
ifstream input("rj.in");
ofstream output("rj.out");
int N , M;
char matrix[NMAX][NMAX];
int distanteR[NMAX][NMAX];
int distanteJ[NMAX][NMAX];
bool isInMatrix(const int & x , const int & y)
{
return (x >= 0) && (x < N) && (y >= 0) && (y < M);
}
void BFS(pair<int,int> startPoint , int distante[NMAX][NMAX])
{
for (int i = 0; i < N ; i++)
for (int j = 0;j < M; j++)
distante[i][j] = -1;
distante[startPoint.first][startPoint.second] = 0;
queue <pair<int,int>> coada;
coada.push(startPoint);
pair<int,int> newPoint , currentPoint;
int dx[] = {-1,1,0,0,1,1,1,-1};
int dy[] = {0,0,-1,1,1,-1,-1,-1};
while (!coada.empty())
{
currentPoint = coada.front();
coada.pop();
for (int i = 0; i < 8 ; i++)
{
newPoint.first = currentPoint.first + dx[i];
newPoint.second = currentPoint.second + dy[i];
if (isInMatrix(newPoint.first,newPoint.second))
{
if (distante[newPoint.first][newPoint.second] == -1 && matrix[newPoint.first][newPoint.second] == ' ')
{
distante[newPoint.first][newPoint.second] = distante[currentPoint.first][currentPoint.second] + 1;
coada.push(newPoint);
}
}
}
}
}
void printMatrix(int matrix[NMAX][NMAX])
{
for (int i = 0; i < N ; i++)
{
cout << '\n';
for (int j = 0; j < M ; j++)
cout << matrix[i][j] << ' ';
}
}
int main()
{
char line[NMAX];
input.getline(line,NMAX);
N = 0 , M = 0;
int poz = 0;
while (line[poz] >= '0' && line[poz] <= '9')
{
N = N * 10 + (line[poz] - '0');
poz ++;
}
poz++;
while (line[poz] >= '0' && line[poz] <= '9')
{
M = M * 10 + (line[poz] - '0');
poz ++;
}
int rx , ry , jx , jy;
for (int i = 0; i < N ; i++)
{
input.getline(matrix[i],NMAX);
for (int j = 0; j < M ; j++)
{
if (matrix[i][j] == 'R')
{
rx = i;
ry = j;
}
if (matrix[i][j] == 'J')
{
jx = i;
jy = j;
}
}
}
BFS(make_pair(rx,ry),distanteR);
printMatrix(distanteR);
BFS(make_pair(jx,jy),distanteJ);
cout << '\n';
printMatrix(distanteJ);
pair<int,int> answerPoint = make_pair(NMAX,NMAX);
int minDist = NMAX * NMAX;
for (int i = 0; i < N ; i++)
for (int j = 0; j < M ; j++)
{
if (distanteJ[i][j] == distanteR[i][j] && distanteJ[i][j] != -1)
{
if (minDist > distanteJ[i][j])
{
minDist = distanteJ[i][j];
answerPoint = make_pair(i,j);
}
else if (minDist == distanteJ[i][j])
{
if (answerPoint.first > i)
{
answerPoint.first = i;
answerPoint.second = j;
}
else if (answerPoint.first == i)
{
answerPoint.second = min(answerPoint.second , j);
}
}
}
}
output << minDist + 1 << ' ' << answerPoint.first + 1 << ' ' << answerPoint.second + 1;
return 0;
}