kburnik

C++ - zadatak MINPATH - BFS

Mar 15th, 2013
73
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <cstdlib>
  3. #include <queue>
  4. #include <set>
  5.  
  6. using namespace std;
  7.  
  8. // dimenzije ploce
  9. int r,s;
  10.  
  11. // igraca ploca
  12. int a[30][30];
  13.  
  14. // uzorak kretanja
  15. int pattern[4][2] = {{-1,0},{0,-1},{0,1},{1,0}};
  16.  
  17. struct pozicija {
  18.    
  19.     int x,y;
  20.    
  21.     pozicija(int _x = 0, int _y = 0) {
  22.         x = _x;
  23.         y = _y;          
  24.     }
  25.    
  26.     // da li je pozicija ispravna (unutar matrice, 0 ili iduci zeton) ?
  27.     bool ispravna(int vrijednost = 0) {
  28.         return (    x >= 0 && x < r
  29.                  && y >= 0 && y < s            
  30.                  && (a[x][y] == 0 || a[x][y] == vrijednost)
  31.                );  
  32.     }
  33.    
  34.     bool jednaka(pozicija p){ return (p.x == x) && (p.y == y); }
  35.    
  36.     pair<int,int> uPar() { return make_pair(x,y); }
  37.  
  38. };
  39.  
  40. struct zeton {    
  41.     pozicija pos;
  42.     int val;
  43.    
  44.     zeton (int _x = 0, int _y = 0, int _val = 0) {
  45.         pos = pozicija( _x , _y );
  46.         val = _val;
  47.     }    
  48. };
  49.  
  50. struct cvor {
  51.     pozicija pos;
  52.     int korak;
  53.    
  54.     cvor(pozicija _pos, int _korak = 0) {
  55.         pos = _pos;
  56.         korak = _korak;    
  57.     }
  58. };
  59.  
  60. ////////////////////////////
  61.  
  62. bool usporedi_zetone(zeton a, zeton b) {
  63.     return a.val < b.val;    
  64. }
  65.  
  66. int bfs(pozicija pocetak, pozicija kraj, int vrijednost){
  67.    
  68.     // cvorovi s pozicijama i udaljenostima, koje posjecujemo
  69.     queue< cvor > q;
  70.    
  71.     // vidjene pozicije
  72.     set < pair<int,int> > vidjeno;
  73.    
  74.     // postavi pocetnu poziciju
  75.     q.push(cvor(pocetak,0));
  76.     vidjeno.insert(pocetak.uPar());
  77.    
  78.     do {
  79.         cvor trenutni = q.front(); q.pop();
  80.                
  81.         if (trenutni.pos.jednaka(kraj)) {
  82.             return trenutni.korak;
  83.         }
  84.        
  85.         for (int i = 0 ; i < 4; i++) {
  86.             pozicija iduca = pozicija(
  87.                   trenutni.pos.x + pattern[i][0]
  88.                 , trenutni.pos.y + pattern[i][1]
  89.             );
  90.            
  91.             if (
  92.                 iduca.ispravna(vrijednost)
  93.                 && ! vidjeno.count( iduca.uPar() )
  94.             ) {
  95.                 vidjeno.insert( iduca.uPar() );
  96.                 cvor iduci = cvor( iduca, trenutni.korak + 1 );
  97.                 q.push( iduci  );
  98.             }
  99.         }
  100.        
  101.     } while ( !q.empty() );
  102.  
  103.     return 0;    
  104.        
  105. }
  106.  
  107. ////////////////////////////
  108.  
  109.  
  110. int main() {
  111.    
  112.    
  113.  
  114.     vector < zeton > v;
  115.        
  116.     cin >> r >> s;
  117.  
  118.     // unesi ploce i zabiljezi zetone
  119.     for (int i = 0 ; i < r; i++ ) {
  120.         for (int j = 0 ; j < s; j++) {
  121.             cin >> a[i][j];
  122.             if (a[i][j] > 0) {
  123.                 v.push_back(zeton(i,j,a[i][j]));
  124.             }
  125.         }
  126.     }
  127.    
  128.     // sortiraj zetone
  129.     sort(v.begin(),v.end(),usporedi_zetone);
  130.    
  131.     // ukupna duljina
  132.     int ukupna = 0;
  133.    
  134.     for (int i = 0; i < v.size()-1; i++) {
  135.         int duljina = bfs( v[i].pos , v[i+1].pos, v[i+1].val );
  136.         if (duljina > 0) {
  137.             // makni zeton
  138.             a[v[i].pos.x][v[i].pos.y] = 0;
  139.            
  140.             // sumiraj duljinu
  141.             ukupna += duljina;
  142.         } else {
  143.             ukupna = 0;
  144.             break;
  145.         }
  146.     }
  147.    
  148.     cout << ukupna << endl;
  149.  
  150.     system("pause");
  151.     return 0;
  152. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×