Cod sursa(job #253334)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 18:02:57
Problema Rj Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.13 kb
 #include <iostream>  
 #include <fstream>  
 #include <list>  
   
 using namespace std;  
   
 int m, n, rl, rc, jl, jc;  
 char *terrain;  
 int *romeoMap, *julietMap;  
   
 inline char& cell(char *map, int line, int col)  
 {  
     return map[line * n + col];  
 }  
   
 inline int& cell(int *map, int line, int col)  
 {  
     return map[line * n + col];  
 }  
   
 void readInput()  
 {  
     FILE *in = fopen("rj.in", "r");  
     fscanf(in, "%d %d\n", &m, &n);  
   
     terrain = new char[m * n];  
     romeoMap = new int[m * n];  
     memset(romeoMap, 0, m * n * sizeof(*romeoMap));  
     julietMap = new int[m * n];  
     memset(julietMap, 0, m * n * sizeof(*julietMap));  
   
     for (int i = 0; i < m; i++) {  
         for (int j = 0; j < n; j++) {  
             cell(terrain, i, j) = fgetc(in);  
             if (cell(terrain, i, j) == 'R') {  
                 rl = i;  
                 rc = j;  
             } else if (cell(terrain, i, j) == 'J') {  
                 jl = i;  
                 jc = j;  
             }  
         }  
         if (i < m - 1) {  
      
            
             while(fgetc(in) != '\n')  
                 ;  
         }  
     }  
     fclose(in);  
 }  
   
 void computeTimes(int *map, int startl, int startc)  
 {  
   
     static const int dl[] = {-1, -1, 0, 1, 1, 1, 0, -1};  
     static const int dc[] = {0, -1, -1, -1, 0, 1, 1, 1};  
     list<int> lst;  
     lst.push_back(startl);  
     lst.push_back(startc);  
   
     while (!lst.empty()) {  
         int l = lst.front();  
         lst.pop_front();  
         int c = lst.front();  
         lst.pop_front();  
         int crtDist = cell(map, l, c);  
   
         for (unsigned int i = 0; i < sizeof(dl) / sizeof(*dl); i++) {  
             int l2 = l + dl[i];  
             int c2 = c + dc[i];  
             if (l2 >= 0 && l2 < m && c2 >= 0 && c2 < n &&  
                     cell(terrain, l2, c2) == ' ' &&  
                     (cell(map, l2, c2) == 0 ||  
                      cell(map, l2, c2) > crtDist + 1)) {  
                 cell(map, l2, c2) = crtDist + 1;  
                 lst.push_back(l2);  
                 lst.push_back(c2);  
             }  
         }  
     }  
 }  
   
 int main()  
 {  
     readInput();  
     computeTimes(romeoMap, rl, rc);  
     computeTimes(julietMap, jl, jc);  
   
     bool found = false;  
     int solCount, solL, solC;  
     for (int i = 0; i < m; i++)  
         for (int j = 0; j < n; j++) {  
             if (cell(romeoMap, i, j) == cell(julietMap, i, j) &&  
                     cell(romeoMap, i, j) != 0) {  
                 if (!found || cell(romeoMap, i, j) < solCount) {  
                     solCount = cell(romeoMap, i, j);  
                     solL = i;  
                     solC = j;  
                 }  
                 found = true;  
             }  
         }  
   
     ofstream out("rj.out");  
     if (!found)  
         out << "0 0 0";  
     else  
         out << solCount + 1 << ' ' << solL + 1 << ' ' << solC + 1;  
     out.close();  
   
     return 0;  
}