Cod sursa(job #357446)

Utilizator vladiiIonescu Vlad vladii Data 19 octombrie 2009 12:09:43
Problema Rj Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 13.72 kb
#include <iostream>
#include <fstream>
#include <list>
#include <queue>
#include <algorithm>
using namespace std;
int BFS(int start, int end);
list<int>G[10000];
int loc;
int main() {
    fstream f1, f2;
    int n, m, i, j, k, l, c, nl, nc, startr, startj, julieta, romeo, min=10000;
    int dl[]={-1, -1, -1, 0, 0, 1, 1, 1};
    int dc[]={-1, 0, 1, -1, 1, -1, 0, 1};
    char v[10000], aux;
    f1.open("rj.in", ios::in);
    f1>>n>>m;
    aux=f1.get();
    for(i=1; i<=n; i++) {
             for(j=1; j<=m; j++) {
                  k=(i-1)*n+j;
                  v[k]=f1.get();
             }
             aux=f1.get();
    }
    f1.close();
    //daca v[i] si " " sunt egale: if(!strcmp(v[i], " "))
    for(i=1; i<=n*m; i++) {
             if(i%n==0) { l=i/n-1; }
             else { l=i/n; }
             if(i%m==0) { c=m; }
             else { c=i%n; } 
             if(v[i]=='R') {
                  startr=i;
             }
             if(v[i]=='J') {
                  startj=i;
             }
             if(v[i]!='X') {
                             //(l-1, c-1), (l-1, c), (l-1, c+1)
                             //(l, c-1), (l, c+1)
                             //(l+1, c-1), (l+1, c), (l+1, c+1)
                             if(i==1) {
                                     k=i+1;
                                     if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                     }
                                     k=i+m;
                                     if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                     }
                                     k=i+m+1;
                                     if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                     }
                             }
                             else if(i==m) {
                                  k=i-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+m-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+m;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                             }
                             else if(i==n*m) {
                                  k=i-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                             }
                             else if(i==(n-1)*m+1) {
                                  k=i+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                             }
                             else if(i<m) {
                                  k=i-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+m-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+m;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+m+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                             }
                             else if(i>(n-1)*m) {
                                  k=i-m-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                             }
                             else if(i%m==0) {
                                  k=i-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+m-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+m;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m-1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-m;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                             }
                             else if(i%m==1) {
                                  k=i-c;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i-c+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+c;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                                  k=i+c+1;
                                  if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                  }
                             }
                             else {
                                 for(j=0; j<8; j++) {
                                      nl=l+dl[j];
                                      nc=c+dc[j];
                                      k=nl*n+nc;
                                      if(v[k]==' ' || v[k]=='R' || v[k]=='J') {
                                                //nodul i si nodul k au muchie comuna
                                                G[i].push_back(k);
                                      }
                                 }
                             }
             }
    }
    for(i=1; i<=n*m; i++) {       
           //startr = casa lui romeo
           //startj = casa julietei
           if(!G[i].empty()) {
                romeo=BFS(i, startr);
                julieta=BFS(i, startj);
                if(romeo==julieta) { if(romeo<min) { min=romeo; loc=i; } }
           }
    }
    if(loc%n==0) { l=loc/n; }
    else { l=loc/n+1; }
    if(loc%m==0) { c=m; }
    else { c=loc%n; } 
    //l, c
    f2.open("rj.out", ios::out);
    f2<<min<<" "<<l<<" "<<c<<endl;
    f2.close();
    return 0;
}


int BFS(int start, int end) {
    int v[10000], cost[10000];
    queue<int> c;
    int p;
    for(int i=1; i<=10000; i++) {
            v[i]=0;
    }
    cost[start]=1;
    c.push(start);
    while(!c.empty()) {
                      p=c.front();
                      for(list<int>::iterator it=G[p].begin();it!=G[p].end();it++) {
                                              if(!v[(*it)]) {
                                                          v[(*it)]=1;
                                                          cost[(*it)]=cost[p]+1;
                                                          if(*it==end) {
                                                                       return cost[(*it)];
                                                          }
                                                          c.push(*it);
                                              }
                      }
                      c.pop();
    }
}