Pagini recente » Concursuri organizate de infoarena | Cod sursa (job #2986591) | Cod sursa (job #1624963) | Cod sursa (job #697850) | Cod sursa (job #2425692)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
bool MAT[MAXN][MAXN];
int DIST[2][MAXN][MAXN];
int N , M;
int dx[] = {1,1,0,-1,-1,-1,0,1 };
int dy[] = {0,-1,-1,-1, 0,-1, 1,1};
void solve (pair < int , int > start , int tip){
queue <pair < int , int > > Q;
Q.push(start);
DIST[tip][start.first][start.second] = 0;
while (!Q.empty()){
pair < int,int > current = Q.front();
Q.pop();
//cout << current.first << " " << current.second << endl;
for (int i = 0;i < 8;i++){
int nextX = current.first + dx[i];
int nextY = current.second + dy[i];
if (nextX < 1 || nextY < 1 || nextX > N || nextY > M ){
continue;
}
if (MAT[nextX][nextY] == true) {
//cout << nextX << " " << nextY << " " << MAT[nextX][nextY] << endl;
continue ;
} else {
}
if (DIST[tip][nextX][nextY] <= DIST[tip][current.first][current.second] + 1){
continue;
}
DIST[tip][nextX][nextY] = DIST[tip][current.first][current.second] + 1;
Q.push({nextX,nextY});
}
//cout << endl;
}
// for (int i = 1; i <= N;i++)
// for (int j = 1; j <= M;j++)
// cout << DIST[tip][i][j] << " \n"[j==M];
// cout << endl;
}
pair < int,int > J,R;
int main(){
ifstream fin("rj.in");
ofstream fout("rj.out");
fin >> N >> M;
string tmp;
getline(fin,tmp);
for (int i = 1;i <= N;i++){
getline(fin, tmp);
for (int j = 0;j < M;j++){
if (tmp[j] == 'R'){
R = {i,j+1};
}
if (tmp[j] == 'J'){
J = {i,j+1};
}
if (tmp[j] == 'X'){
MAT[i][j+1] = true;
}
DIST[0][i][j+1] = 1e9;
DIST[1][i][j+1] = 1e9;
}
}
for (int i = 1; i <= N;i++)
for (int j = 1; j <= M;j++)
cout << MAT[i][j] << " \n"[j==M];
cout << endl;
solve(R, 1);
solve(J, 0);
int MIN = 1e9;
pair <int,int> minIndex;
for (int i = 1;i <= N;i++){
for (int j = 1;j <= M;j++){
if (DIST[0][i][j] == DIST[1][i][j] && MIN > DIST[0][i][j]){
MIN = DIST[0][i][j];
minIndex = {i,j};
}
}
}
fout << MIN + 1 << " " << minIndex.first << " " <<minIndex.second;
return 0;
}