Pagini recente » Cod sursa (job #1371008) | Cod sursa (job #245329) | Cod sursa (job #2951168) | Cod sursa (job #2497576) | Cod sursa (job #2425644)
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 110;
int N, M;
int MAT[MAXN][MAXN];
int DR[MAXN][MAXN], DJ[MAXN][MAXN];
pair<int,int> ROMEO, JULIET;
const int MAX_VAL = 10;
bool isValid(pair<int,int> pos) {
if (pos.first >= 1 && pos.first <= N &&
pos.second <= M && pos.second >= 1 && MAT[pos.first][pos.second] != MAX_VAL) return true;
return false;
}
pair<int,int> start;
pair<int,int> finish;
void bfs(pair<int,int> start, int dist[MAXN][MAXN]){
int dx[] = {1,1,0,-1,-1,-1,0,1 };
int dy[] = {0,-1,-1,-1, 0,-1, 1,1};
queue<pair<int,int> > Q;
Q.push(start);
dist[start.first][start.second] = 0;
while (!Q.empty()) {
pair<int,int> curr = Q.front();
Q.pop();
for (int k = 0 ; k < 8;k++){
int nextX = curr.first + dx[k];
int nextY = curr.second + dy[k];
//cout << nextX << " " << nextY << endl;
if (isValid({nextX, nextY})) {
if (dist[nextX][nextY] == 0) {
dist[nextX][nextY] = dist[curr.first][curr.second] + 1;
Q.push({nextX, nextY});
} else if (dist[curr.first][curr.second] + 1 < dist[nextX][nextY]) {
dist[nextX][nextY] = dist[curr.first][curr.second] + 1;
}
}
}
}
dist[start.first][start.second] = 0;
for (int i = 1; i <= N;i++)
for (int j = 1; j <= M; j++) {
if( dist[i][j] == MAX_VAL) dist[i][j] = 0;
cout << dist[i][j] << " \n"[j==M];
}
cout << endl;
}
int main () {
ifstream fin("rj.in");
ofstream cout("rj.out");
fin >> N>> M;
//fin.get();
for (int i = 0; i <= N;i++) {
string tmp;
getline(fin, tmp);
for (int j = 0; j < tmp.size();j++) {
switch (tmp[j]){
case 'R':
start = {i, j + 1};
MAT[i][j + 1] = 2;
break;
case 'J':
finish = {i, j + 1};
MAT[i][j + 1] = 3;
break;
case 'X':
MAT[i][j + 1] = DJ[i][j + 1] = DR[i][j + 1] = MAX_VAL;
default:
break;
}
}
}
bfs(start, DR);
bfs(finish, DJ);
int minVal = MAX_VAL;
pair<int,int> minIndex;
for (int i = 1; i <= N;i++)
for(int j = 1; j <= M;j++) {
if (DJ[i][j] != 0 && DR[i][j] != 0)
if (max(DJ[i][j], DR[i][j]) < minVal) {
minVal = max(DJ[i][j], DR[i][j]);
minIndex = {i,j};
}
//minVal = min(minVal, DJ[i][j] + DR[i][j]);
}
int i = minIndex.first, j = minIndex.second;
cout << min(DJ[i][j], DR[i][j]) + 1 <<" ";
cout << minIndex.first << " " << minIndex.second;
return 0;
}