Pagini recente » Cod sursa (job #2148218) | Cod sursa (job #3283941) | Cod sursa (job #2624772) | Istoria paginii runda/oji_2014_10 | Cod sursa (job #1119320)
///RJ
#include<fstream>
#include<vector>
#include<utility>
#include<queue>
#include<limits>
#include<string>
using namespace std;
typedef pair<short, short> PSHORT;
struct COORD
{
short x;
short y;
};
short map[5][5];///vector< vector<short> > map;
queue<PSHORT> q;
COORD result_coord;
short result_time=numeric_limits<short>::max();
bool ok(short x, short y)
{
if(map[y][x]==-1)
return false;
else
if(map[y][x]<map[q.front().second][q.front().first]+1)
return false;
else
return true;
}
bool found(short x,short y)
{
if(map[y][x]==map[q.front().second][q.front().first]+1 && result_time>map[q.front().second][q.front().first]+1)
return true;
else
return false;
}
int main()
{
ifstream fin("rj.in");
ofstream fout("rj.out");
short N, M; ///m-sor
string test;
fin>>M>>N;
fin.get();
///map.resize(M);
///for(short i=0; i<M; i++)
///map[i].resize(N);
for(short i=0; i<M; i++)
{
getline(fin, test);
for(short j=0; j<N; j++)
switch(test[j])
{
case ' ': map[i][j]=numeric_limits<short>::max(); break;
case 'R': map[i][j]=0; q.push(PSHORT(j, i)); break;
case 'J': map[i][j]=0; q.push(PSHORT(j, i)); break;
case 'X': map[i][j]=-1; break;
}
}
short x_temp, y_temp;
while(!q.empty())
{
x_temp=q.front().first+1;
y_temp=q.front().second;
if(x_temp<N && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
x_temp=q.front().first+1;
y_temp=q.front().second-1;
if(x_temp<N && y_temp>=0 && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
x_temp=q.front().first;
y_temp=q.front().second-1;
if(y_temp>=0 && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
x_temp=q.front().first-1;
y_temp=q.front().second-1;
if(x_temp>=0 && y_temp>=0 && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
x_temp=q.front().first-1;
y_temp=q.front().second;
if(x_temp>=0 && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
x_temp=q.front().first-1;
y_temp=q.front().second+1;
if(x_temp>=0 && y_temp<M && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
x_temp=q.front().first;
y_temp=q.front().second+1;
if(x_temp<M && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
x_temp=q.front().first+1;
y_temp=q.front().second+1;
if(x_temp<N && y_temp<M && ok(x_temp, y_temp))
{
if(found(x_temp, y_temp))
{
result_coord.x=x_temp;
result_coord.y=y_temp;
result_time=map[q.front().second][q.front().first]+1;
}
map[y_temp][x_temp]=map[q.front().second][q.front().first]+1;
q.push(PSHORT(x_temp, y_temp));
}
q.pop();
}
fout<<result_time+1<<' '<<result_coord.y+1<<' '<<result_coord.x+1<<'\n';
return 0;
}