Pagini recente » Cod sursa (job #3168360) | Cod sursa (job #1183425) | Cod sursa (job #2734456) | Cod sursa (job #1693916) | Cod sursa (job #1096521)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
const int NMAX = 100;
using namespace std;
ifstream input("rj.in");
ofstream output("rj.out");
int N , M;
char matrix[NMAX][NMAX];
int distante[NMAX][NMAX];
queue <pair<int,int>> coada;
bool isInMatrix(const int & x , const int & y)
{
return (x >= 0) && (x < N) && (y >= 0) && (y < M);
}
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 ++;
}
for (int i = 0; i < N ; i++)
{
input.getline(matrix[i],NMAX);
for (int j = 0; j < M ; j++)
{
distante[i][j] = -1;
if (matrix[i][j] == 'R')
{
coada.push(make_pair(i,j));
distante[i][j] = 0;
}
if (matrix[i][j] == 'J')
{
coada.push(make_pair(i,j));
distante[i][j] = 0;
}
}
}
pair<int,int> newPoint , currentPoint , answerPoint = make_pair(NMAX,NMAX);
int minDist = NMAX * NMAX;
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 (matrix[newPoint.first][newPoint.second] == ' ')
{
if(matrix[currentPoint.first][currentPoint.second] == 'R')
{
matrix[newPoint.first][newPoint.second] = 'R';
distante[newPoint.first][newPoint.second] = distante[currentPoint.first][currentPoint.second] + 1;
coada.push(newPoint);
}
else if (matrix[currentPoint.first][currentPoint.second] == 'J')
{
matrix[newPoint.first][newPoint.second] = 'J';
distante[newPoint.first][newPoint.second] = distante[currentPoint.first][currentPoint.second] + 1;
coada.push(newPoint);
}
}
else if ((matrix[newPoint.first][newPoint.second] == 'R' && matrix[currentPoint.first][currentPoint.second] == 'J') || (matrix[newPoint.first][newPoint.second] == 'J' && matrix[currentPoint.first][currentPoint.second] == 'R'))
{
if (distante[newPoint.first][newPoint.second] > distante[currentPoint.first][currentPoint.second])
{
if (distante[newPoint.first][newPoint.second] < minDist)
{
minDist = distante[newPoint.first][newPoint.second];
answerPoint = newPoint;
}
else if (distante[newPoint.first][newPoint.second] == minDist)
{
if (answerPoint.first > newPoint.first) answerPoint = newPoint;
else if (answerPoint.first == newPoint.first && answerPoint.second > newPoint.second) answerPoint = newPoint;
}
matrix[newPoint.first][newPoint.second] = 'T';
}
else
{
if (distante[currentPoint.first][currentPoint.second] < minDist)
{
minDist = distante[currentPoint.first][currentPoint.second];
answerPoint = currentPoint;
}
else if (distante[currentPoint.first][currentPoint.second] == minDist)
{
if (answerPoint.first > currentPoint.first) answerPoint = currentPoint;
else if (answerPoint.first == currentPoint.first && answerPoint.second > currentPoint.second) answerPoint = currentPoint;
}
matrix[currentPoint.first][currentPoint.second] = 'T';
}
}
}
}
}
output << minDist + 1 << ' ' << answerPoint.first + 1 << ' ' << answerPoint.second + 1;
return 0;
}