Pagini recente » Cod sursa (job #2259357) | Cod sursa (job #2949626) | Cod sursa (job #2417200) | Cod sursa (job #824821) | Cod sursa (job #1632335)
#include <iostream>
#include <fstream>
#include <cstring>
#include <queue>
#include <string>
using namespace std;
int mat[101][101];
int m, n;
int minim = 10000;
int di[] = { -1, 0, 1, 0 };
int dj[] = { 0, 1, 0, -1 };
ifstream i("rj.in");
ofstream o("rj.out");
struct pos
{
int x, y;
};
int drum(int x, int y)
{
if(mat[x][y] == minim + 1)
{
o << x << " " << y;
return 0;
}
int j,k, t;
t = 10000;
pos l;
for(int a = 0; a < 4; a++)
{
j = x + di[a];
k = y + dj[a];
if( (mat[j][k] < t) && (mat[j][k] > 0) )
{
t = mat[j][k];
l.x = j;
l.y = k;
}
}
return drum(l.x, l.y);
}
int main()
{
string k;
pos start;
pos finish;
i >> m >> n;
getline(i, k);
for(int a = 1; a <= m; a++)
{
getline(i, k);
char j[100];
strcpy(j, k.c_str());
for(int b = 1; b <= n; b++)
{
if(j[b - 1] == 'X')
{
mat[a][b] = -1;
}
else if(j[b - 1] == ' ')
{
mat[a][b] = 0;
}
else if(j[b - 1] == 'R')
{
start.x = a;
start.y = b;
mat[a][b] = 1;
}
else if(j[b - 1] == 'J')
{
mat[a][b] = -2;
}
}
}
for(int a = 0; a <= n; a++)
{
mat[a][0] = -1;
mat[a][m + 1] = -1;
}
for(int a = 0; a <= m; a++)
{
mat[0][a] = -1;
mat[n + 1][a] = -1;
}
queue<pos> coada;
coada.push(start);
while(!coada.empty())
{
pos curr = coada.front();
coada.pop();
for(int a = 0; a < 4; a++)
{
int x = curr.x + di[a];
int y = curr.y + dj[a];
if(mat[x][y] == 0)
{
mat[x][y] = mat[curr.x][curr.y] + 1;
pos t;
t.x = x;
t.y = y;
coada.push(t);
}
if(mat[x][y] == -2)
{
if(mat[curr.x][curr.y] < minim)
{
minim = mat[curr.x][curr.y];
}
finish.x = x;
finish.y = y;
}
}
}
if(minim)
{
minim = minim / 2;
}
else
{
minim = minim / 2 + 1;
}
o << minim << " ";
drum(finish.x, finish.y);
return 0;
}