Pagini recente » Cod sursa (job #189609) | Cod sursa (job #2663393) | Cod sursa (job #479178) | Cod sursa (job #522763) | Cod sursa (job #2125401)
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>
#define INFINITY 999999999
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct Point {
int line;
int col;
};
bool notOutOfMatrix(int line, int col);
void uniformSearch(Point start, int costMatrix[101][101]);
int lines, cols;
Point startP, endP;
bool matrix[101][101]; // true - can't get there, false - can get there
int costR[101][101];
int costJ[101][101];
int main() {
char line[101];
fin.getline(line, 10, '\n');
istringstream str(line);
str >> lines >> cols;
str.clear();
for (int l = 0; l < lines; ++l) {
fin.getline(line, cols * 2);
for (int c = 0; c < cols; ++c) {
if (line[c] == 'R') {
startP.line = l;
startP.col = c;
} else if (line[c] == 'J') {
endP.line = l;
endP.col = c;
} else if (line[c] == 'X') {
matrix[l][c] = true;
}
}
}
for (int l = 0; l < lines; ++l) {
for (int c = 0; c < cols; ++c) {
costR[l][c] = INFINITY;
costJ[l][c] = INFINITY;
}
}
uniformSearch(startP, costR);
uniformSearch(endP, costJ);
// for (int l = 0; l < lines; ++l) {
// for (int c = 0; c < cols; ++c) {
// fout << costJ[l][c] << ' ';
// }
// fout << '\n';
// }
// fout << '\n';
//
// for (int l = 0; l < lines; ++l) {
// for (int c = 0; c < cols; ++c) {
// fout << costR[l][c] << ' ';
// }
// fout << '\n';
// }
Point minPoint = {-1, -1};
int minCost = INFINITY;
for (int l = 0; l < lines; ++l) {
for (int c = 0; c < cols; ++c) {
if (minCost > costJ[l][c] and costJ[l][c] == costR[l][c] and costJ[l][c] != INFINITY) {
minPoint = {l, c};
minCost = costJ[l][c];
}
}
}
fout << minCost << ' ' << minPoint.line + 1 << ' ' << minPoint.col + 1 << '\n';
return 0;
}
void uniformSearch(Point start, int costMatrix[101][101]) {
queue<Point> frontier;
frontier.push(start);
costMatrix[start.line][start.col] = 1;
int dx[] = {0, -1, -1, -1, 0, 1, 1, 1};
int dy[] = {1, -1, 0, 1, 1, 1, 0, -1};
while (!frontier.empty()) {
Point current = frontier.front();
frontier.pop();
for (int iter = 0; iter < 8; ++iter) {
Point next = {current.line + dx[iter], current.col + dy[iter]};
if (!matrix[next.line][next.col] and notOutOfMatrix(next.line, next.col)) {
int newCost = costMatrix[current.line][current.col] + 1;
if (costMatrix[next.line][next.col] == INFINITY or newCost < costMatrix[next.line][next.col]) {
costMatrix[next.line][next.col] = newCost;
frontier.push(next);
}
}
}
}
}
bool notOutOfMatrix(int line, int col) {
return line >= 0 and line < lines and col >= 0 and col < cols;
}