Pagini recente » Cod sursa (job #1345811) | Cod sursa (job #1245428) | Cod sursa (job #587296) | Cod sursa (job #1765100) | Cod sursa (job #2226175)
#include <queue>
#include <iostream>
#include <fstream>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
istream & in = fin;
ostream & out = fout;
struct vec2{
typedef int type;
type x, y;
vec2()
{}
vec2(type x, type y) : x(x), y(y)
{}
vec2 & operator+=(const vec2 & rhs)
{
this->x += rhs.x;
this->y += rhs.y;
return *this;
}
vec2 & operator-=(const vec2 & rhs)
{
this->x -= rhs.x;
this->y -= rhs.y;
return *this;
}
vec2 operator*=(const type & rhs)
{
this->x *= rhs;
this->y *= rhs;
return *this;
}
vec2 operator/=(const type & rhs)
{
this->x /= rhs;
this->y /= rhs;
return *this;
}
bool in_bounds(vec2 vec)
{
return (this->x >= 1 && this->y >= 1 && this->x <= vec.x && this->y <= vec.y);
}
};
vec2 operator-(vec2 lhs)
{
lhs.x = -lhs.x;
lhs.y = -lhs.y;
return lhs;
}
vec2 operator+(vec2 lhs, const vec2 & rhs)
{
lhs += rhs;
return lhs;
}
vec2 operator-(vec2 lhs, const vec2 & rhs)
{
lhs -= rhs;
return lhs;
}
vec2 operator*(vec2 lhs, const vec2::type & rhs)
{
lhs *= rhs;
return lhs;
}
vec2 operator/(vec2 lhs, const vec2::type & rhs)
{
lhs /= rhs;
return lhs;
}
ostream & operator<<(ostream & lhs, const vec2 & rhs)
{
lhs << "(" << rhs.x << "," << rhs.y << ")";
return lhs;
}
vec2 size;
vec2 r, j;
int rmat[114][114], jmat[114][114];
vec2 dir[] = {vec2(-1, -1), vec2(0, -1), vec2(1, -1), vec2(1, 0), vec2(1, 1), vec2(0, 1), vec2(-1, 1), vec2(-1, 0)};
vec2 pos;
int dist = -1;
int conv(char c)
{
if(c == 'R' || c == 'J'){
return 1;
}else if(c == ' '){
return 0;
}else if(c == 'X'){
return -1;
}
}
void read()
{
in >> size.y >> size.x;
in.get();
char c;
for(int y = 1; y <= size.y; y++){
for(int x = 1; x <= size.x; x++){
c = in.get();
if(c == 'R'){
r = vec2(x, y);
}else if(c == 'J'){
j = vec2(x, y);
}
rmat[x][y] = jmat[x][y] = conv(c);
}
while(in.get() != '\n' && !in.eof());
}
rmat[j.x][j.y] = jmat[r.x][r.y] = 0;
}
void brucelee(vec2 start, int mat[114][114])
{
queue<vec2> qu;
qu.push(start);
vec2 curr, neckst;
while(!qu.empty()){
curr = qu.front();
qu.pop();
for(int i = 0; i < 8; i++){
neckst = curr;
neckst += dir[i];
if(neckst.in_bounds(size) && mat[neckst.x][neckst.y] == 0){
mat[neckst.x][neckst.y] = mat[curr.x][curr.y] + 1;
qu.push(neckst);
}
}
}
}
void findy()
{
for(int y = 1; y <= size.y; y++){
for(int x = 1; x <= size.x; x++){
if(rmat[x][y] == jmat[x][y] && rmat[x][y] > 0){
if(dist == -1){
dist = rmat[x][y];
}else{
dist = min(dist, rmat[x][y]);
}
pos = vec2(x, y);
}
}
}
}
void solve()
{
brucelee(r, rmat);
brucelee(j, jmat);
findy();
}
void write()
{
out << dist << " " << pos.y << " " << pos.x;
}
int main()
{
read();
solve();
write();
}