Pagini recente » Cod sursa (job #1559277) | Cod sursa (job #1695717) | Cod sursa (job #2850059) | Cod sursa (job #688234) | Cod sursa (job #674137)
Cod sursa(job #674137)
#include <fstream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAX 105
#define INF 20000
using namespace std;
typedef struct coada
{
short val;
char x, y;
};
vector<coada> romeo, julieta;
int n,m;
char matrice[MAX][MAX];
short r[MAX][MAX], j[MAX][MAX];
char depl_x[] = {-1, -1, 0, 1, 1, 1, 0, -1};
char depl_y[] = {0, 1, 1, 1, 0, -1, -1, -1};
int bestX, bestY, best = INF;
void citire()
{
ifstream in("rj.in");
in>>n>>m;
in.get();
int i, h;
coada a;
for(i = 0; i < n; i++)
{
in.getline(matrice[i], MAX);
matrice[i][strlen(matrice[i])] = '\n';
for(h = 0; h < m; h++)
{
if(matrice[i][h] == 'R')
{
r[i][h] = 1;
a.val = 1;
a.x = i;
a.y = h;
romeo.push_back(a);
}
else if(matrice[i][h] == 'J')
{
j[i][h] = 1;
a.val = 1;
a.x = i;
a.y = h;
julieta.push_back(a);
}
}
}
in.close();
}
void leeRomeo()
{
int a = 0;
int i;
coada nou;
while(a < romeo.size())
{
for(i = 0; i < 8; i++)
{
if(romeo[a].x + depl_x[i] < n && romeo[a].x + depl_x[i] >= 0 &&
romeo[a].y + depl_y[i] < m && romeo[a].y + depl_y[i] >= 0 &&
matrice[romeo[a].x + depl_x[i]][romeo[a].y + depl_y[i]] != 'X' &&
r[romeo[a].x + depl_x[i]][romeo[a].y + depl_y[i]] == INF)
{
nou.x = romeo[a].x + depl_x[i];
nou.y = romeo[a].y + depl_y[i];
nou.val = romeo[a].val + 1;
romeo.push_back(nou);
r[romeo[a].x + depl_x[i]][romeo[a].y + depl_y[i]] = nou.val;
}
}
a++;
}
}
void leeJulieta()
{
int a = 0;
int i;
coada nou;
while(a < julieta.size())
{
for(i = 0; i < 8; i++)
{
if(julieta[a].x + depl_x[i] < n && julieta[a].x + depl_x[i] >= 0 &&
julieta[a].y + depl_y[i] < m && julieta[a].y + depl_y[i] >= 0 &&
j[julieta[a].x + depl_x[i]][julieta[a].y + depl_y[i]] == INF &&
matrice[julieta[a].x + depl_x[i]][julieta[a].y + depl_y[i]] != 'X')
{
nou.x = julieta[a].x + depl_x[i];
nou.y = julieta[a].y + depl_y[i];
nou.val = julieta[a].val + 1;
julieta.push_back(nou);
j[julieta[a].x + depl_x[i]][julieta[a].y + depl_y[i]] = nou.val;
}
}
a++;
}
}
void findSolution()
{
int i, h;
for(i = 0; i < n; i++)
{
for(h = 0; h < m; h++)
{
if(r[i][h] == j[i][h] && r[i][h] < best)
{
best = r[i][h];
bestX = i;
bestY = h;
}
}
}
}
void afisare()
{
ofstream out("rj.out");
out<<best<<" "<<bestX + 1<<" "<<bestY + 1;
}
void init()
{
int i, h;
for(i = 0; i < n; i++)
{
for(h = 0; h < m; h++)
{
r[i][h] = j[i][h] = INF;
}
}
r[romeo[0].x][romeo[0].y] = 1;
j[julieta[0].x][julieta[0].y] = 1;
}
int main()
{
citire();
init();
leeRomeo();
leeJulieta();
findSolution();
afisare();
return 0;
}