Pagini recente » Cod sursa (job #1350781) | Cod sursa (job #2728894) | Cod sursa (job #2389662) | Cod sursa (job #1976771) | Cod sursa (job #2124583)
#include <iostream>
#include <fstream>
#include <sstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
struct Point {
int line;
int col;
};
int lines, cols;
Point startP, endP;
bool matrix[101][101]; // true - can't get there, false - can get there
Point cameFrom[101][101];
int main() {
int lines, cols;
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;
}
}
}
queue<Point> frontier;
frontier.push(startP);
for (int l = 0; l < lines; ++l) {
for (int c = 0; c < cols; ++c) {
cameFrom[l][c] = {-1, -1};
}
}
cameFrom[startP.line][startP.col] = {-2, -2};
// cameFrom[endP.line][endP.col] = {-2, -2};
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();
if (current.line == endP.line and current.col == endP.col) {
break;
}
for (int iter = 0; iter < 8; ++iter) {
Point next = {current.line + dx[iter], current.col + dy[iter]};
if (!matrix[next.line][next.col]) {
if (cameFrom[next.line][next.col].line == -1 and cameFrom[next.line][next.col].col == -1) {
frontier.push(next);
cameFrom[next.line][next.col] = current;
}
}
}
}
Point current = endP;
int time = 0;
Point history[10005];
history[0] = current;
while (current.line != startP.line and current.col != startP.col) {
current = cameFrom[current.line][current.col];
time++;
history[time] = current;
}
int ind = time / 2;
if(time % 2 == 1)
time++;
fout << time / 2 + 1 << ' ' << history[ind].line + 1 << ' ' << history[ind].col + 1 << '\n';
//
// for (int l = 0; l < lines; ++l) {
// for (int c = 0; c < cols; ++c) {
// cout << '(' << cameFrom[l][c].line << ',' << cameFrom[l][c].col << ") ";
// }
// cout << '\n';
// }
// cout << startP.line << ' ' << startP.col << '\n';
// cout << endP.line << ' ' << endP.col << '\n';
return 0;
}