Mai intai trebuie sa te autentifici.
Cod sursa(job #1894672)
Utilizator | Data | 27 februarie 2017 12:34:20 | |
---|---|---|---|
Problema | Rj | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva de probleme | Marime | 2.97 kb |
#include <iostream>
#include <fstream>
#include <queue>
#include <math.h>
using namespace std;
struct punct
{
int x,y;
};
void citire(int &n,int &m,char **&M)
{
ifstream fin("rj.in");
fin>>n>>m;
M=new char* [n+1];
int i,j;
for(i=1;i<=n;i++)
M[i]=new char [m+1];
for(i=1;i<=n;i++){
fin.get();
for(j=1;j<=m;j++)
fin.get(M[i][j]);
}
fin.close();
}
void lee(char **M,punct r,punct j,int n,int m)
{
queue <punct> c1,c2;
c1.push(r);
c2.push(j);
punct a,b,a1,b1;
int i;
int oriz[8]={1,1,1,0,0,-1,-1,-1};
int vert[8]={0,1,-1,1,-1,0,1,-1};
while(!c1.empty() || !c2.empty())
{
if(!c1.empty());
a=c1.front();
if(!c2.empty())
b=c2.front();
for(i=0;i<8;i++)
{
a1.x=a.x+oriz[i];
a1.y=a.y+vert[i];
if(a1.x>0 && a1.x<n+1 && a1.y>0 && a1.y<m+1)
if(M[a1.x][a1.y]==' ' || M[a1.x][a1.y]=='J')
{
//cout<<a1.x<<" "<<a1.y<<"\n";
c1.push(a1);
if(M[a1.x][a1.y]=='J')
M[a1.x][a1.y]='Z';
else
M[a1.x][a1.y]='R';
}
}
for(i=0;i<8;i++)
{
b1.x=b.x+oriz[i];
b1.y=b.y+vert[i];
if(b1.x>0 && b1.x<n+1 && b1.y>0 && b1.y<m+1){
if(M[b1.x][b1.y]==' ' || M[b1.x][b1.y]=='R')
{
// cout<<b1.x<<" "<<b1.y<<"\n";
c2.push(b1);
if(M[b1.x][b1.y]=='R')
M[b1.x][b1.y]='Z';
else
M[b1.x][b1.y]='J';
}
}
}
c1.pop();
c2.pop();
}
}
int distanta_Manhattan(punct a,punct b)
{
return fabs(a.x-b.x)+fabs(a.y-b.y);
}
int main()
{
char **M;
int n,m;
citire(n,m,M);
punct r,jl;
int i,j,sw=0;
for(i=1;i<=n;i++){
if(sw==3)
break;
for(j=1;j<=m;j++){
if(M[i][j]=='R')
{
sw++;
r.x=i;
r.y=j;
}
if(M[i][j]=='J')
{
sw++;
jl.x=i;
jl.y=j;
}
if(sw==2){
break;
sw=3;}
}
}
lee(M,r,jl,n,m);
punct a;
int minn=m*n,xmin,ymin;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(M[i][j]=='Z')
{
a.x=i;
a.y=j;
if(distanta_Manhattan(r,a)==distanta_Manhattan(jl,a))
if(minn>distanta_Manhattan(r,a))
{
minn=distanta_Manhattan(r,a);
xmin=a.x;
ymin=a.y;
}
}
ofstream fout("rj.out");
fout<<minn<<" "<<xmin<<" "<<ymin<<" "<<'\n';
fout.close();
return 0;
}