Pagini recente » Cod sursa (job #2098789) | Cod sursa (job #3162171) | Cod sursa (job #2695911) | Cod sursa (job #1509310) | Cod sursa (job #2542517)
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
queue < pair < int , int > > q;
int n,m;
int mat[105][105];
char sir[105];
int adiac1[105][105];
int adiac2[105][105];
int linrom,colrom,linjul,coljul;
int dx[5]={0,-1,0,1,0}, dy[5]={0,0,1,0,-1};
int lin,col;
int dist;
void bordare() {
for (int i=1;i<=n;i++) {
mat[i][0]=-1;
mat[i][m+1]=-1;
}
for (int j=1;j<=m;j++) {
mat[0][j]=-1;
mat[n+1][j]=-1;
}
}
void lee1() {
while (q.empty()==0) {
lin = q.front().first;
col= q.front().second;
for (int k=1;k<=4;k++) {
if (mat[lin+dx[k]][col+dy[k]]==0 && (adiac1[lin+dx[k]][col+dy[k]]>adiac1[lin][col]+1 || adiac1[lin+dx[k]][col+dy[k]]==0)) {
adiac1[lin+dx[k]][col+dy[k]]=adiac1[lin][col]+1;
q.push(make_pair(lin+dx[k],col+dy[k]));
}
}
q.pop();
}
}
void lee2() {
while (q.empty()==0) {
lin = q.front().first;
col= q.front().second;
for (int k=1;k<=4;k++) {
if (mat[lin+dx[k]][col+dy[k]]==0 && (adiac2[lin+dx[k]][col+dy[k]]>adiac2[lin][col]+1 || adiac2[lin+dx[k]][col+dy[k]]==0)) {
adiac2[lin+dx[k]][col+dy[k]]=adiac2[lin][col]+1;
q.push(make_pair(lin+dx[k],col+dy[k]));
}
}
q.pop();
}
}
int main()
{
f >> n >> m;
f.get();
bordare();
for (int i=1;i<=n;i++) {
f.getline(sir,100);
for (int j=0;j<strlen(sir);j++) {
if (sir[j]==' ') {
mat[i][j+1]=0;
}
else if (sir[j]=='X') {
mat[i][j+1]=-1;
}
else if (sir[j]=='R') {
linrom=i;
colrom=j+1;
mat[i][j+1]=0;
}
else if(sir[j]=='J') {
linjul=i;
coljul=j+1;
mat[i][j+1]=0;
}
}
}
q.push(make_pair(linjul,coljul));
adiac1[linjul][coljul]=1;
lee1();
q.push(make_pair(linrom,colrom));
adiac2[linrom][colrom]=1;
lee2();
/*for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
g << mat[i][j];
}
g <<'\n';
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
g << adiac1[i][j];
}
g <<'\n';
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
g << adiac2[i][j];
}
g <<'\n';
}
g << linjul <<" "<<coljul<<" "<<linrom<<" "<<colrom<<" " <<adiac1[linrom][colrom];
*/
/*dist = adiac1[linrom][colrom]+1;
dist/=2;
int ok=0;
for (int i=1;i<=n && ok==0;i++) {
for (int j=1;j<=m && ok==0;j++) {
if (adiac1[i][j]==dist && adiac2[i][j]==dist) {
g << dist-1 <<" " << i <<" "<< j;
ok=1;
}
}
}
*/
dist=adiac1[linrom][colrom];
if (dist&2==1) {
dist++;
dist/=2;
int ok=0;
for (int i=1;i<=n && ok==0;i++) {
for (int j=1;j<=m && ok==0;j++) {
if (adiac1[i][j]==dist && adiac2[i][j]==dist) {
g << dist-1 <<" " << i <<" "<< j;
ok=1;
}
}
}
}
else {
int dist1=((dist+1)/2)+1;
int dist2=((dist+1)/2);
int ok=0;
for (int i=1;i<=n && ok==0;i++) {
for (int j=1;j<=m && ok==0;j++) {
if ((adiac1[i][j]==dist1 && adiac2[i][j]==dist2) || (adiac1[i][j]==dist2 && adiac2[i][j]==dist1)) {
g << dist2-1 <<" " << i <<" "<< j;
ok=1;
}
}
}
}
return 0;
}