#if 0
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
int a[105][105], n, m, nrMarcei;
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, 1, 0, -1 };
///ifstream fin("insule.in");
///ofstream fout("insule.out");
struct poz
{
int x, y;
poz(int x, int y)
:x(x), y(y)
{
}
};
bool inside(int i, int j)
{
return i >= 1 && i <= n && j >= 1 && j <= m;
}
void showCh()
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (a[i][j] == -1)
{
cout << '#';
}
else if (a[i][j] == 0)
{
cout << '.';
}
else if (a[i][j] == 1)
{
cout << 'M';
}
else if (a[i][j] == -2)
{
cout << '@';
}
cout << ' ';
}
cout << '\n';
}
}
void show()
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
if (a[i][j] == -1)
{
cout << '#';
}
else if (a[i][j] == -2)
{
cout << '@';
}
else
{
cout << a[i][j];
}
cout << ' ';
}
cout << '\n';
}
}
int lee2(queue <poz>q)
{
while (!q.empty())
{
int ii = q.front().x;
int jj = q.front().y;
for (int k = 0; k < 4; ++k)
{
int iii = ii + dx[k];
int jjj = jj + dy[k];
if (inside(iii, jjj))
{
if (a[iii][jjj] == 0)
{
a[iii][jjj] = a[ii][jj] + 1;
q.push(poz(iii, jjj));
}
else if (a[iii][jjj] == 1)
{
--nrMarcei;
q.push(poz(iii, jjj));
}
}
}
q.pop();
}
return 0;
}
/**
##########
#M.#....M#
#M.#.....#
#.#......#
##......M#
#........#
#..M....##
#....M.#M#
##########
*/
int main()
{
queue <poz> q;
int t, i, j;
char ch;
cin >> t;
while (t--)
{
cin >> n >> m;
nrMarcei = 0;
for (i = 0; i < n; ++i)
{
for (j = 0; j < m; ++j)
{
cin >> ch;
if (ch == '#')
a[i][j] = -1;
else if (ch == '.')
a[i][j] = 0;
else if (ch == 'M')
{
a[i][j] = 1;
++nrMarcei;
q.push(poz(i, j));
}
}
}
lee2(q);
show();
}
return 0;
}
#endif // 0
#include <iostream>
#include <cstring>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("rj.in");
ofstream fout("rj.out");
int dx[] = {-1, -1, 0, 1, 1, 1, 0, -1};
int dy[] = { 0, 1, 1, 1, 0, -1, -1, -1};
int n, m;
struct idk
{
int val, drum;
};
idk a[105][105];
struct Vec2
{
int x, y;
};
bool inb(int a, int b)
{
return 0 <= a && a < n && 0 <= b && b < m;
}
void show()
{
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j)
{
cout << a[i][j].val << ' ';
}
cout << '\n';
}
}
Vec2 lee(queue <Vec2>& q)
{
int x, y, xx, yy, xfin = -1, yfin = -1;
bool ok = 0;
while (!q.empty())
{
x = q.front().x;
y = q.front().y;
for (int k = 0; k < 8; ++k)
{
xx = x + dx[k];
yy = y + dy[k];
if (inb(xx, yy))
{
if (a[xx][yy].val == 0 && a[xx][yy].drum == 0)
{
a[xx][yy].val = a[x][y].val + 1;
a[xx][yy].drum = a[x][y].drum;
q.push({xx, yy});
}
if (a[xx][yy].val == a[x][y].val + 1 && a[xx][yy].drum == -1 * a[x][y].drum && ok == 0)
{
ok = 1;
xfin = xx;
yfin = yy;
}
if (a[xx][yy].val == a[x][y].val + 1 && a[xx][yy].drum == -1 * a[x][y].drum && a[xx][yy].val == a[xfin][yfin].val && yy < yfin)
{
xfin = xx;
yfin = yy;
}
}
}
q.pop();
}
return {xfin, yfin};
}
int main()
{
queue <Vec2> q;
int i, j;
char ch[101];
fin >> n >> m;
fin.get();
for (i = 0; i < n; ++i)
{
fin.getline(ch, m + 1);
for (j = 0; j < m; ++j)
{
if (ch[j] == 'X')
{
a[i][j] = {-1, 0};
}
else if (ch[j] == ' ')
{
a[i][j] = {0, 0};
}
else if (ch[j] == 'R')
{
a[i][j] = {1, 1};
q.push({i, j});
}
else if (ch[j] == 'J')
{
a[i][j] = {1, -1};
q.push({i, j});
}
}
}
Vec2 v = lee(q);
fout << a[v.x][v.y].val << ' ' << v.x + 1 << ' ' << v.y + 1;
return 0;
}
/**
T:
Campion: impozit, sqr, fib, descfib, ech
Infoarena: next
pbinfo: pilula
Campion: radical, sumb, pm, numar4, doctor, munte1, dale
PbInfo: #287, #290, #292, #505, #1321
UVA: 465, 619, 748, 10083, 10523
UVA: 11849, 501
PbInfo: roata
*/