Pagini recente » Cod sursa (job #2682869) | Cod sursa (job #1605974) | Cod sursa (job #1648110) | Cod sursa (job #2706690) | Cod sursa (job #2781776)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
int h; int w;
struct Point
{
int x = 0;
int y = 0;
int getIndex() { return x + y * h; }
void setFromIndex(int i) { x = i % w; y = i / h; }
};
int main()
{
std::ifstream in("rj.in");
in >> h >> w;
char notUsed=0;
in.read(¬Used, 1);
char mat[100][100];
Point romeo;
Point juliet;
for (int y = 0; y < h; y++)
{
char line[101] = {};
in.read(line, w + 1);
for (int x = 0; x < w; x++)
{
mat[y][x] = line[x];
if (line[x] == 'R')
{
romeo = {x,y};
}
else if (line[x] == 'J')
{
juliet = {x,y};
}
}
}
in.close();
std::vector<char> visited;
visited.resize(w * h);
std::vector<int> returnPath; //this will trace any node back to "from" using the shortest path
returnPath.resize(w*h, -1);
auto romeoIndex = romeo.getIndex();
auto julietIndex = juliet.getIndex();
visited[romeoIndex] = 1;
std::queue<Point> nodesToVisit; //current node
nodesToVisit.emplace(romeo);
bool found = 0;
while (!nodesToVisit.empty() && !found)
{
auto point = nodesToVisit.front();
nodesToVisit.pop();
std::vector<Point> vecini;
vecini.reserve(8);
if (point.x < w - 1 && point.y > 0) { vecini.push_back({point.x + 1, point.y - 1}); }
if (point.y > 0) { vecini.push_back({point.x, point.y - 1}); }
if (point.x > 0 && point.y > 0) { vecini.push_back({point.x - 1, point.y - 1}); }
if (point.x > 0) { vecini.push_back({point.x - 1, point.y}); }
if (point.x > 0 && point.y < h - 1) { vecini.push_back({point.x - 1, point.y + 1}); }
if (point.x < w - 1) { vecini.push_back({point.x + 1, point.y}); }
if (point.y < h - 1) { vecini.push_back({point.x, point.y + 1}); }
if (point.x < w - 1 && point.y < h - 1) { vecini.push_back({point.x + 1, point.y + 1}); }
for (auto i = 0; i < vecini.size(); i++)
{
int index = vecini[i].getIndex();
if (visited[index] == 0 && mat[vecini[i].y][vecini[i].x] != 'X')
{
visited[index] = 1;
nodesToVisit.push(vecini[i]);
returnPath[index] = point.getIndex();
if (
vecini[i].x == juliet.x &&
vecini[i].y == juliet.y
)
{
found = true;
break;
}
}
}
}
std::vector<int> returnVector;
returnVector.reserve(200);
{
int el = returnPath[julietIndex];
returnVector.push_back(julietIndex);
while (el >= 0)
{
returnVector.push_back(el);
el = returnPath[el];
}
}
//for (auto i : returnVector)
//{
// Point p;
// p.setFromIndex(i);
// std::cout << p.x << " " << p.y << "\n";
//}
std::ofstream out("rj.out");
int s = returnVector.size() / 2;
Point p;
p.setFromIndex(returnVector[s]);
out << s + 1 << " ";
out << p.y + 1 << " " << p.x + 1;
out.close();
//std::cin.get();
return 0;
}