Pagini recente » Cod sursa (job #2322106) | Cod sursa (job #2575257) | Cod sursa (job #1201447) | Cod sursa (job #1504291) | Cod sursa (job #1889498)
#include <iostream>
#include <fstream>
#include <vector>
#include <vector>
#include <queue>
using namespace std;
int n, m, a[105][105], xR, yR, xJ, yJ;
char mat[150][150];
vector <int> vJ, vR, q[10001];
void citire(){
fstream f("rj.in",ios::in);
f >> n >> m;
int i, j;
f.getline(mat[0],150,'\n');
for(i = 0;i < n; ++i)
f.getline(mat[i],150,'\n');
for(i = 0;i <= n + 1; ++i)
a[i][m + 1] = a[i][0] = 0;
for(i = 0;i <= m + 1; ++i)
a[n + 1][i] = a[0][i] = 0;
for(i = 0;i < n; ++i){
for(j = 0;j < m; ++j){
if(mat[i][j] == 'J'){
xJ = i + 1;
yJ = j + 1;
a[i + 1][j + 1] = -1;
continue;
}
if(mat[i][j] == 'R'){
xR = i + 1;
yR = j + 1;
a[i + 1][j + 1] = -1;
continue;
}
if(mat[i][j] == ' '){
a[i + 1][j + 1] = 1;
continue;
}
if(mat[i][j] == 'X'){
a[i + 1][j + 1] = 0;
continue;
}
}
}
f.close();
}
void liniarizare(){
int i, j;
for(i = 1;i <= n; ++i)
for(j = 1;j <= m; ++j){
if(a[i][j]){
if(a[i + 1][j]){
q[(i-1) * n + j].push_back(i * n + j);
q[i * n + j].push_back((i-1) * n + j);
}
if(a[i][j + 1]){
q[(i-1) * n + j].push_back((i-1) * n + j + 1);
q[(i-1) * n + j + 1].push_back((i-1) * n + j);
}
if(a[i + 1][j + 1]){
q[i * n + j + 1].push_back((i-1) * n + j);
q[(i-1) * n + j].push_back(i * n + j + 1);
}
if(a[i - 1][j]){
q[(i-1) * n + j].push_back((i - 2) * n + j);
q[(i - 2) * n + j].push_back((i-1) * n + j);
}
if(a[i][j - 1]){
q[(i-1) * n + j].push_back((i-1) * n + j - 1);
q[(i-1) * n + j - 1].push_back((i-1) * n + j);
}
if(a[i - 1][j - 1]){
q[(i-1) * n + j].push_back((i - 2) * n + j - 1);
q[(i - 2) * n + j - 1].push_back((i-1) * n + j);
}
if(a[i - 1][j + 1]){
q[(i-1) * n + j].push_back((i - 2) * n + j + 1);
q[(i - 2) * n + j + 1].push_back((i-1) * n + j);
}
if(a[i + 1][j - 1]){
q[(i-1) * n + j].push_back(i * n + j - 1);
q[i * n + j - 1].push_back((i-1) * n + j);
}
}
}
}
void print(vector <int> vJ){
fstream g("rj.out",ios::out);
int mid = vJ.size() / 2 + 1, x, y;
g << mid << " ";
x = vJ[mid] / n;
if(vJ[mid] % m)
++n;
y = vJ[mid] % m;
g << x << " " << y;
g.close();
}
void BFS(int nod,vector <int> v[10001],vector <int> p,int final){
queue <int> qu;
int vizitat[n * m], i, S, tata[n * m];
for(i = 1;i <= n * m; ++i)
vizitat[i] = tata[i] = -1;
qu.push(nod);
tata[nod] = 0;
while(!qu.empty()){
S = qu.front();
qu.pop();
vizitat[S] = 1;
if(S == final)
break;
int len = v[S].size();
for(i = 0;i < len; ++i)
if(vizitat[v[S][i]] == -1){
qu.push(v[S][i]);
vizitat[v[S][i]] = 1;
tata[v[S][i]] = S;
}
}
int x;
x = final;
while(x){
p.push_back(x);
x = tata[x];
}
print(p);
}
int main(){
citire();
liniarizare();
BFS((xJ-1) * n + yJ,q,vJ,(xR-1) * n + yR);
//BFS((xR-1) * n + yR,q,vR,(xJ-1) * n + yJ);
}