Cod sursa(job #412433)

Utilizator Mastertrap21Danceanu Madalin Mastertrap21 Data 5 martie 2010 17:16:07
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.59 kb
#include <fstream>
#include <queue>
struct punct{ int ff; int ss; };
using namespace std;

ifstream f("rj.in");
ofstream g("rj.out");

int A[101][101], n, m;

punct start, end;

const int dx[] = {0, 1, 0, -1, 1, -1, -1, 1};
const int dy[] = {1, 0, -1, 0, 1, -1, 1, -1};


void citire()
{
f>>n>>m;
f.get();
for(int x=1;x<=n;x++) {
char text[101];
f.getline(text,100);
for(int j=1;j<=m;j++) {
switch(int(text[j-1]))
{
case 82: {
	start.ff=x;
	start.ss=j;
	A[x][j]=1;
	break;
	}
	
case 74: {
	end.ff=x;
	end.ss=j;
	A[x][j]=-2;
	break;
	}
	
case 88: {
	A[x][j]=-1;
	break;
	}

case 32: {
	A[x][j]=-2;
	break;
	}
}
}
}
for(int i=0;i<=n;i++) A[i][0]=A[i][n+1]=A[0][i]=A[n+1][i]=-1;
}

int lee(){
	int i;
	
	
	queue<punct> Q;
	punct now, now2;
	
	Q.push(start);
	
	while (Q.empty() == false)
	{
	now.ff = Q.front().ff;
	now.ss = Q.front().ss;
	Q.pop();
	if ( now.ff == end.ff && now.ss == end.ss  ) return A[end.ff][end.ss];
	for (i = 0; i < 8; i++){
	now2.ff = now.ff + dx[i];
	now2.ss= now.ss + dy[i];
	
	if (A[now2.ff][now2.ss] == -2){
				A[now2.ff][now2.ss] = A[now.ff][now.ss] + 1;
				Q.push(now2);
			}
		}
	}
	
	return -1;
	
}

int parc(int i, int j, int nr)
{
int ii, jj, reza=0, rezb=0;
for(int x=0;x<8;x++)
{
ii=i+dx[x];
jj=j+dy[x];
if(A[ii][jj]==nr-1) reza=1;
if(A[ii][jj]==nr+1) rezb=1;
}
if(reza&&rezb) return 1;
return 0;
}

int main()
{
int nr;
citire();
nr=(lee()+1)/2;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(A[i][j]==nr) if(parc(i,j,nr)) g<<nr<<" "<<i<<" "<<j; }
f.close();
g.close();
return 0;
}