Cod sursa(job #1408369)

Utilizator handsonthewheelSandel Georgel handsonthewheel Data 30 martie 2015 00:00:19
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <fstream>
#include <queue>
#include <cstring>
#define N 109
using namespace std;
ifstream cin ("rj.in");
ofstream cout ("rj.out");
int dist[N][N], dist2[N][N];
char a[N][N];
char seen[N][N];
queue <pair <int, int> > q;
inline bool isInside (int n, int m, pair <int, int> p ){
    return (p.first > 0 && p.second > 0 && p.first <=n && p.second <=m);
}
void Lee(int n, int m){
const int dx[]={0, -1, 0, 1, -1, -1, 1, 1};
const int dy[]={-1, 0, 1, 0, -1, 1, 1, -1};
while (!q.empty()){
        pair <int, int> v = q.front();
        q.pop();
        for (int k = 0 ; k < 8; ++k){
                pair <int, int> w = make_pair(v.first+dx[k], v.second + dy[k]);
        if (isInside(n,m,w) && a[w.first][w.second] != 'X' && !seen[w.first][w.second]){
                seen[w.first][w.second] = 1;
        dist[w.first][w.second]=dist[v.first][v.second]+1;
        q.push(w);}
        }
}
}
void Lee2(int n, int m){
const int dx[]={0, -1, 0, 1, -1, -1, 1, 1};
const int dy[]={-1, 0, 1, 0, -1, 1, 1, -1};
while (!q.empty()){
        pair <int, int> v = q.front();
        q.pop();
        for (int k = 0 ; k < 8; ++k){
                pair <int, int> w = make_pair(v.first+dx[k], v.second + dy[k]);
        if (isInside(n,m,w) && a[w.first][w.second] != 'X' && !seen[w.first][w.second]){
                seen[w.first][w.second] = 1;
        dist2[w.first][w.second]=dist2[v.first][v.second]+1;
        q.push(w);}
        }
}
}
int main(){
    int n, m, i, j;
    char pp;
    cin >> n >> m;
    memset (dist,99999,sizeof(dist));
    for (i = 1 ; i <= n; ++i){
    cin.get();
    cin.get(a[i]+1,N);
    }
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
        if (a[i][j] == 'X') dist[i][j] = -1, dist2[i][j] = -1;}
    for (i=1;i<=n;i++)
    for (j=1;j<=m;j++){
            if (a[i][j] == 'R') {
                memset(seen,0,sizeof(seen));
            q.push(make_pair(i,j));
                dist[i][j] = 1;
                a[i][j]='X';
            seen[i][j] = 1;
                    Lee(n,m);
                    a[i][j]='R';}
    }
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
        if (a[i][j] == 'J'){
                memset(seen,0,sizeof(seen));
                while (!q.empty()){
                    q.pop();}
        q.push(make_pair(i,j));
        a[i][j]='X';
        dist2[i][j]=1;
        seen[i][j]=1;
        a[i][j] = 'J';
        Lee2(n,m);}
}
pair <int,int> s;
int min = 999999;
for (i=1;i<=n;i++)
for (j=1;j<=m;j++){
        if (dist[i][j]==dist2[i][j]&&dist[i][j]<min&&a[i][j]!='X'){
                min=dist[i][j];
                s = make_pair(i,j);}
}
cout<<min<<" "<<s.first<<" "<<s.second;
}