Pagini recente » Cod sursa (job #1984899) | Cod sursa (job #1466876) | Cod sursa (job #1471393) | Cod sursa (job #578337) | Cod sursa (job #2868592)
#pragma region Header
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <unordered_map>
#include <chrono>
#include <map>
#include <thread>
#include <mutex>
#include <future>
typedef unsigned long long ull;
typedef long long ll;
typedef unsigned int uint;
#define endl '\n'
using namespace std;
#if 1
#include <fstream>
ifstream fin("rj.in");
ofstream fout("rj.out");
#define cin fin
#define cout fout
#endif
#pragma endregion
const int nmx = 1e2+3;
int a[nmx][nmx];
int n,m;
int resi,resj;
int tmin = INT_MAX;
int ri,rj;
int ji,jj;
struct Pct
{
int i,j;
};
int d[nmx][nmx];
int& Depth(Pct p)
{
return d[p.i][p.j];
}
int viz[nmx][nmx];
void Bfs()
{
queue<Pct> q;
q.push({ri,rj});
q.push({ji,jj});
viz[ri][rj] = viz[ji][jj] = 2;
Pct off[] = {{0,1},{1,0},{-1,0},{0,-1}};
while(q.empty() == false)
{
Pct frnt = q.front();
q.pop();
for (int i =0;i<4;i++)
{
Pct npz = {frnt.i + off[i].i,frnt.j + off[i].j};
if( npz.i < 1 || npz.j < 1 || npz.i > n || npz.j > m || a[npz.i][npz.j] == 1)
continue;
if(viz[npz.i][npz.j] == 1)
{
if(Depth(frnt)+1 == Depth(npz))/// possible solution
{
int t = Depth(npz);
if(t < tmin)
{
tmin = t;
resi = npz.i;
resj = npz.j;
}
else if (t == tmin)
{
if(npz.i < resi)
{
resi = npz.i;
resj = npz.j;
}
else if (npz.i == resi)
{
if(npz.j < resj)
{
resi = npz.i;
resj = npz.j;
}
}
}
}
continue;
}
else if (viz[npz.i][npz.j] == 2)
continue;
d[npz.i][npz.j] = Depth(frnt) + 1;
viz[npz.i][npz.j] = 1;
q.push(npz);
}
}
}
// conditie: linia punctului minima,
// apoi coloana minima
int main()
{
cin >> n >> m;
cin.ignore(200,'\n');
for (int i=1;i<=n;i++)
{
char buf[nmx+1]{};
cin.getline(buf,nmx);
for(int j=1;j<=m;j++)
{
char x = buf[j-1];
if(x == 'R')
{
ri = i;
rj = j;
continue;
}
else if (x == 'J')
{
ji = i;
jj = j;
continue;
}
a[i][j] = (x=='X' ? 1 : 0);
}
}
Bfs();
cout << tmin << " " << resi << " " << resj;
}