Pagini recente » Cod sursa (job #2011423) | Cod sursa (job #1250820) | Cod sursa (job #2408941) | Cod sursa (job #1594804) | Cod sursa (job #530445)
Cod sursa(job #530445)
#include<iostream>
#include<fstream>
#include<queue>
using namespace std;
ifstream f("rj.in");
ofstream g("rj.out");
int a[102][102],optr[102][102],optj[102][102],n,m,i,j,istr,istj,jstr,jstj,x,y,tmin=1000000;
queue<int>qxr,qyr,qxj,qyj;
void citire()
{
int i,j;
char buf[200];
f>>n>>m;
f.getline(buf,102);
for(i=1;i<=n;i++)
{
f.getline(buf,114);
for (j=0;j<m;j++)
{
if (buf[j]=='X') a[i][j+1]=1;
if (buf[j]=='R') a[i][j+1]=2;
if (buf[j]=='J') a[i][j+1]=3;
}
}
}
int main()
{
citire();
/*
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
cout << a[i][j] << " ";
cout << '\n';
}
*/
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(a[i][j]==2)
{
istr=i;
jstr=j;
}
else
if(a[i][j]==3)
{
istj=i;
jstj=j;
}
for(i=0;i<=m+1;i++)
a[0][i]=a[n+1][i]=1;
for(i=1;i<=n-1;i++)
a[i][0]=a[i][m+1]=1;
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
optr[i][j]=n*m+1;
optr[istr][jstr]=1;
qxr.push(istr);
qyr.push(jstr);
while(!qxr.empty())
{
int ic,jc,iv,jv;
ic=qxr.front();
jc=qyr.front();
qxr.pop();
qyr.pop();
iv=ic+1;jv=jc;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
iv=ic-1;jv=jc;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
iv=ic;jv=jc+1;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
iv=ic;jv=jc-1;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
iv=ic-1;jv=jc-1;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
iv=ic-1;jv=jc+1;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
iv=ic+1;jv=jc-1;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
iv=ic+1;jv=jc+1;
if(a[iv][jv]==0)
if(optr[ic][jc]+1<optr[iv][jv])
{
optr[iv][jv]=optr[ic][jc]+1;
qxr.push(iv);
qyr.push(jv);
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
optj[i][j]=n*m+1;
optj[istj][jstj]=1;
qxj.push(istj);
qyj.push(jstj);
while(!qxj.empty())
{
int ic,jc,iv,jv;
ic=qxj.front();
jc=qyj.front();
qxj.pop();
qyj.pop();
iv=ic+1;jv=jc;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
iv=ic-1;jv=jc;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
iv=ic;jv=jc+1;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
iv=ic;jv=jc-1;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
iv=ic-1;jv=jc-1;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
iv=ic-1;jv=jc+1;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
iv=ic+1;jv=jc-1;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
iv=ic+1;jv=jc+1;
if(a[iv][jv]==0)
if(optj[ic][jc]+1<optj[iv][jv])
{
optj[iv][jv]=optj[ic][jc]+1;
qxj.push(iv);
qyj.push(jv);
}
}
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(optr[i][j]==optj[i][j]&&optr[i][j]<tmin)
{
tmin=optr[i][j];
x=i;
y=j;
}
cout<<tmin<<' '<<x<<' '<<y;
g<<tmin<<' '<<x<<' '<<y<<'\n';
return 0;
}
/*
5 5
R XX
X X X
X XXX
X X X
X J X
*/