Pagini recente » Cod sursa (job #2883281) | Cod sursa (job #1456518) | Cod sursa (job #2764714) | Cod sursa (job #2453113) | Cod sursa (job #1996330)
#include <fstream>
#include <queue>
#include <algorithm>
#define INFINITE 2000000
#define DIMENSION 110
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int n, m;
queue < pair <int, int> > st;
bool a[DIMENSION][DIMENSION];
int b[DIMENSION][DIMENSION];
int c[DIMENSION][DIMENSION];
char s[DIMENSION];
int xr, yr, xj, yj;
void Bord_Matrix()
{
for (int i = 0;i <= n + 1;i++)
a[i][0] = a[i][m + 1] = true;
for (int i = 0;i <= m + 1;i++)
a[0][i] = a[n + 1][i] = true;
}
void Lee(int matrix[][DIMENSION],int X,int Y)
{
int i, j, x, y;
int dx[] = {0,0,1,-1,-1,-1,1,1};
int dy[] = {1,-1,0,0,-1,1,-1,1};
st.push(make_pair(X, Y));
while (!st.empty())
{
/*pair<int, int> aux = st.front();
i = aux.first;
j = aux.second;*/
i = st.front().first;
j = st.front().second;
st.pop();
for (int k = 0;k < 8;k++)
{
x = i + dx[k];
y = j + dy[k];
if (a[x][y] == false && matrix[x][y] > matrix[i][j] + 1)
{
matrix[x][y] = matrix[i][j] + 1;
st.push(make_pair(x, y));
}
}
}
}
/*
void Display_Matrix(int x)
{
if(x==1)
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
cout << a[i][j] << "\t";
cout << "\n";
}
if(x==2)
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
cout << b[i][j] << "\t";
cout << "\n";
}
if (x == 3)
for (int i = 1;i <= n;i++)
{
for (int j = 1;j <= m;j++)
cout << c[i][j] << "\t";
cout << "\n";
}
cout << "\n";
}
*/
void Solution()
{
int minim = INFINITE;
pair<int, int> poz;
for (int i = 1;i <= n;i++)
{
for (int j = 1; j <= m; j++)
{
if ((b[i][j] != INFINITE && c[i][j] != INFINITE) && b[i][j] < minim && b[i][j] == c[i][j])
{
minim = b[i][j];
poz.first = i;
poz.second = j;
}
}
}
g << minim << " " << poz.first << " " << poz.second << "\n";
}
int main()
{
f >> n >> m;
f.get();
for (int i = 1;i <= n;i++)
{
f.getline(s+1, DIMENSION);
for (int j = 1;j<=m;j++)
{
b[i][j] = INFINITE;
c[i][j] = INFINITE;
if (s[j] == ' ')
a[i][j] = false;
if (s[j] == 'X')
a[i][j] = true;
if (s[j] == 'R')
{
xr = i;
yr = j;
a[i][j] = false;
b[i][j] = 1;
}
if (s[j] == 'J')
{
xj = i;
yj = j;
a[i][j] = false;
c[i][j] = 1;
}
}
}
Bord_Matrix();
Lee(b,xr,yr);
Lee(c,xj,yj);
//Display_Matrix(1);
//Display_Matrix(2);
//Display_Matrix(3);
Solution();
// de facut doua lee uri
// de tinut cont de cazul special cand nu se intalnesc pe aceeasi pozitie
f.close();
g.close();
return 0;
}