Pagini recente » Cod sursa (job #692314) | Cod sursa (job #2257989) | Cod sursa (job #3215083) | Cod sursa (job #1176091) | Cod sursa (job #1140466)
#include<iostream>
#include<fstream>
#include<stdio.h>
#include<string.h>
using namespace std;
struct str
{
int x,y;
}r,ju;
bool test(int i,int j,str *coada,str *coa);
void citire(int &n,int &m,int **&a,char *fis)
{
FILE *f;
f=fopen(fis,"r");
fscanf(f,"%d%d",&n,&m);
int i,j;
a=new int *[n+1];
for(i=0;i<=n;i++)
{
a[i]=new int[m+1];
a[i][0]=0;
}
char aa[n+1][m+1];
for(i=0;i<=n;i++) fgets(aa[i],m+2,f);
//for (i=0;i<m;i++) cout<<i<<aa[1][i];
//for(i=0;i<=n;i++) {cout<<i;puts(aa[i]);}
int k=1;
for(i=1;i<=n;i++)
for(j=0;j<m;j++)
switch(aa[i][j])
{
case 'R': {a[i][j+1]=0;r.x=i;r.y=j+1;}break;
case 'J': {a[i][j+1]=0;ju.x=i;ju.y=j+1;}break;
case ' ': a[i][j+1]=0;break;
case 'X': a[i][j+1]=-1;break;
}
fclose(f);
}
int main()
{
int n,m,**a;
citire(n,m,a,"rj.in");
int i,j;
str coada[10001];
int viz[101][101],k=0,l=0;
for(i=0;i<=100;i++)
for(j=0;j<=100;j++) viz[i][j]=0;
coada[l]=r;
viz[coada[l].x][coada[l].y]=1;
a[coada[l].x][coada[l].y]=1;
while(l>=k)
{
if(coada[k].x-1>=1)
if(!viz[coada[k].x-1][coada[k].y]&&!a[coada[k].x-1][coada[k].y])
{coada[++l].x=coada[k].x-1;
coada[l].y=coada[k].y;
viz[coada[k].x-1][coada[k].y]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
if(coada[k].x+1<=n)
if(!viz[coada[k].x+1][coada[k].y]&&!a[coada[k].x+1][coada[k].y])
{coada[++l].x=coada[k].x+1;
coada[l].y=coada[k].y;
viz[coada[k].x+1][coada[k].y]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
if(coada[k].y-1>=1)
if(!viz[coada[k].x][coada[k].y-1]&&!a[coada[k].x][coada[k].y-1])
{coada[++l].x=coada[k].x;
coada[l].y=coada[k].y-1;
viz[coada[k].x][coada[k].y-1]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
if(coada[k].y+1<=m)
if(!viz[coada[k].x][coada[k].y+1]&&!a[coada[k].x][coada[k].y+1])
{coada[++l].x=coada[k].x;
coada[l].y=coada[k].y+1;
viz[coada[k].x][coada[k].y+1]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
if(coada[k].x-1>=1&&coada[k].y-1>=1)
if(!viz[coada[k].x-1][coada[k].y-1]&&!a[coada[k].x-1][coada[k].y-1])
{coada[++l].x=coada[k].x-1;
coada[l].y=coada[k].y-1;
viz[coada[k].x-1][coada[k].y-1]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
if(coada[k].x+1<=n&&coada[k].y-1>=1)
if(!viz[coada[k].x+1][coada[k].y-1]&&!a[coada[k].x+1][coada[k].y-1])
{coada[++l].x=coada[k].x+1;
coada[l].y=coada[k].y-1;
viz[coada[k].x+1][coada[k].y-1]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
if(coada[k].x+1<=n&&coada[k].y+1<=m)
if(!viz[coada[k].x+1][coada[k].y+1]&&!a[coada[k].x+1][coada[k].y+1])
{coada[++l].x=coada[k].x+1;
coada[l].y=coada[k].y+1;
viz[coada[k].x+1][coada[k].y+1]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
if(coada[k].x-1>=1&&coada[k].y+1<=m)
if(!viz[coada[k].x-1][coada[k].y+1]&&!a[coada[k].x-1][coada[k].y+1])
{coada[++l].x=coada[k].x-1;
coada[l].y=coada[k].y+1;
viz[coada[k].x-1][coada[k].y+1]=1;
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
}
//cout<<coada[k].x<<" "<<coada[k].y<<"\n";
k++;
}
str coa[10001];
for(i=0;i<=10000;i++)
{
coa[i]=coada[i];
coada[i].x=coada[i].y=0;
}
for(i=0;i<=100;i++)
for(j=0;j<=100;j++) viz[i][j]=0;
k=l=0;
coada[l]=ju;
viz[coada[l].x][coada[l].y]=1;
a[coada[l].x][coada[l].y]=1;
while(l>=k)
{
if(coada[k].x-1>=1)
if(!viz[coada[k].x-1][coada[k].y]&&a[coada[k].x-1][coada[k].y]!=-1)
{coada[++l].x=coada[k].x-1;
coada[l].y=coada[k].y;
viz[coada[k].x-1][coada[k].y]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
if(coada[k].x+1<=n)
if(!viz[coada[k].x+1][coada[k].y]&&a[coada[k].x+1][coada[k].y]!=-1)
{coada[++l].x=coada[k].x+1;
coada[l].y=coada[k].y;
viz[coada[k].x+1][coada[k].y]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
if(coada[k].y-1>=1)
if(!viz[coada[k].x][coada[k].y-1]&&a[coada[k].x][coada[k].y-1]!=-1)
{coada[++l].x=coada[k].x;
coada[l].y=coada[k].y-1;
viz[coada[k].x][coada[k].y-1]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
if(coada[k].y+1<=m)
if(!viz[coada[k].x][coada[k].y+1]&&a[coada[k].x][coada[k].y+1]!=-1)
{coada[++l].x=coada[k].x;
coada[l].y=coada[k].y+1;
viz[coada[k].x][coada[k].y+1]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
if(coada[k].x-1>=1&&coada[k].y-1>=1)
if(!viz[coada[k].x-1][coada[k].y-1]&&a[coada[k].x-1][coada[k].y-1]!=-1)
{coada[++l].x=coada[k].x-1;
coada[l].y=coada[k].y-1;
viz[coada[k].x-1][coada[k].y-1]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
if(coada[k].x+1<=n&&coada[k].y-1>=1)
if(!viz[coada[k].x+1][coada[k].y-1]&&a[coada[k].x+1][coada[k].y-1]!=-1)
{coada[++l].x=coada[k].x+1;
coada[l].y=coada[k].y-1;
viz[coada[k].x+1][coada[k].y-1]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
if(coada[k].x+1<=n&&coada[k].y+1<=m)
if(!viz[coada[k].x+1][coada[k].y+1]&&a[coada[k].x+1][coada[k].y+1]!=-1)
{coada[++l].x=coada[k].x+1;
coada[l].y=coada[k].y+1;
viz[coada[k].x+1][coada[k].y+1]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
if(coada[k].x-1>=1&&coada[k].y+1<=m)
if(!viz[coada[k].x-1][coada[k].y+1]&&a[coada[k].x-1][coada[k].y+1]!=-1)
{coada[++l].x=coada[k].x-1;
coada[l].y=coada[k].y+1;
viz[coada[k].x-1][coada[k].y+1]=1;
if(a[coada[l].x][coada[l].y]!=a[coada[k].x][coada[k].y]+1)
a[coada[l].x][coada[l].y]=a[coada[k].x][coada[k].y]+1;
else break;
}
//cout<<coada[k].x<<" "<<coada[k].y<<"\n";
k++;
}
/*
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
printf("%2d ",a[i][j]);
cout<<"\n";
}
*/
ofstream g("rj.out");
bool z=1;
for(i=1;i<=n&&z;i++)
for(j=1;j<=m&&z;j++)
if(a[coada[l].x][coada[l].y]==a[i][j]&&test(i,j,coada,coa)) {g<<a[coada[l].x][coada[l].y]<<" "<<i<<" "<<j;z=0;}
g.close();
return 0;
}
bool test(int i,int j,str *coada,str *coa)
{
bool c=1,d=1;
for(int k=0;k<=10000&&c;k++) if(i==coada[k].x&&j==coada[k].y) c=0;
for(int k=0;k<=10000&&d;k++) if(i==coa[k].x&&j==coa[k].y) d=0;
//cout<<c<<" "<<d<<"\n";
if(c==0&&d==0) return 1;
return 0;
}