Pagini recente » Cod sursa (job #1110433) | Cod sursa (job #2842421) | Cod sursa (job #3029920) | Cod sursa (job #1630355) | Cod sursa (job #1925211)
#include <fstream>
#include <vector>
#include <list>
#include <queue>
#include <cstring>
#include <utility>
using namespace std;
ifstream in("rj.in");
ofstream out("rj.out");
vector< list<int> > adiac;
struct cell
{
int x, y;
};
int lines, cols, dist;
cell Romeo, Julieta;
void build_graph()
{
in >> lines >> cols;
char *buffer = new char[cols + 1];
char *prev = new char[cols + 1];
adiac.resize(lines * cols);
int k = 0;
for (int i = 0; i < lines; ++i)
{
in.getline(buffer, cols + 1);
if (strlen(buffer) != 0)
{
int length = strlen(buffer);
while (length < cols)
{
buffer[length] = ' ';
++length;
}
buffer[length] = '\0';
for (int j = 0; j < cols; ++j)
{
if (buffer[j] == 'R')
{
Romeo.x = i;
Romeo.y = j;
}
else if (buffer[j] == 'J')
{
Julieta.x = i;
Julieta.y = j;
}
if (buffer[j] != 'X')
{
if (i != 0)
{
if (j != 0)
{
if (prev[j - 1] != 'X')
{
adiac[k].push_back(k - cols - 1);
adiac[k - cols - 1].push_back(k);
}
}
if (j != cols - 1)
{
if (prev[j + 1] != 'X')
{
adiac[k].push_back(k - cols + 1);
adiac[k - cols + 1].push_back(k);
}
}
if (prev[j] != 'X')
{
adiac[k].push_back(k - cols);
adiac[k - cols].push_back(k);
}
}
if (j != 0)
{
if (buffer[j - 1] != 'X')
{
adiac[k].push_back(k - 1);
adiac[k - 1].push_back(k);
}
}
}
++k;
}
strcpy(prev, buffer);
}
else
--i;
}
}
void write_graph()
{
int k = 0;
for (vector< list<int> >::iterator it = adiac.begin(); it != adiac.end(); ++it)
{
if ((*it).size() != 0)
{
out << k <<": ";
for (list<int>::iterator jt = (*it).begin(); jt != (*it).end(); ++jt)
{
out << *jt << ' ';
}
out << '\n';
}
++k;
}
}
int BF_meet_position() {
queue< pair<int, int> > q;
vector<short> viz;
vector<int> father;
viz.resize(lines * cols, 0);
bool ok = true;
father.resize(lines * cols, -1);
int start_node = (lines - 1) * Romeo.x + Romeo.y;
father[start_node] = -2;
int final_node = (lines - 1) * Julieta.x + Julieta.y;
q.push(make_pair(start_node, 1));
q.push(make_pair(final_node, 2));
while (!q.empty())
{
int curr_node = q.front().first;
int choice = q.front().second;
viz[curr_node] = (viz[curr_node] != 0) ? viz[curr_node] : choice;
for (list<int>::iterator it = adiac[curr_node].begin(); it != adiac[curr_node].end(); ++it)
{
if (viz[*it] != 0 && viz[*it] != choice)
{
final_node = *it;
//father[*it] = curr_node;
ok = false;
break;
}
else if (viz[*it] != choice)
{
q.push(make_pair(*it, choice));
if (choice == 1)
father[*it] = curr_node;
}
}
q.pop();
if (!ok)
break;
}
start_node = final_node;
dist = 0;
do {
++dist;
start_node = father[start_node];
} while(start_node != -2 && father[start_node] != -2);
return final_node;
}
int main()
{
build_graph();
int node = BF_meet_position(), k = 0;
vector<cell> normalized_vec(lines * cols);
for (int i = 0; i < lines; ++i)
for (int j = 0; j < cols; ++j)
{
normalized_vec[k].x = i;
normalized_vec[k++].y = j;
}
out << dist << " " << normalized_vec[node].x + 1 << " " << normalized_vec[node].y + 1;
return 0;
}