Advertisement
Deerenaros

Breadth-first search in C++

Jun 27th, 2012
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <stdio.h>
  4. #include <mem.h>
  5.  
  6. int *find(int *m, int n);
  7. inline int abs(int x){return (x < 0) ? -x : x;}
  8.  
  9. int start = 0;
  10. int finish = 0;
  11.  
  12. //#define DEBUG
  13.  
  14. int main(int argc, char **argv){
  15.     if(argc > 1)
  16.         freopen(argv[1], "r", stdin);
  17.     else
  18.         freopen("in.txt", "r", stdin);
  19.     int n; std::cin >> n >> start >> finish;
  20.     int *matrix = new int[n*n];
  21.     for(int i = 0; i < n*n; i++) std::cin >> matrix[i];
  22.     int *p = find(matrix, n);
  23.     if(p != NULL)
  24.         for(int i = 1; i <= p[0]; i++) std::cout << p[i] << " ";
  25.     else
  26.         std::cout << "No way from start to finish";
  27.     std::cout << std::endl;
  28.    
  29.     delete p;
  30.     return 0;
  31. }
  32.  
  33. int* find(int *m, int n){
  34.     int q[2*n], vis[n], restore[n];
  35.     unsigned ql = 0, qr = 0;
  36.     for(int i = 0; i < n; i++) vis[i] = -1;
  37.     q[qr++] = start;        //q.push(start)
  38.     vis[start] = 0;
  39.     restore[start] = -1;
  40.     while(qr != ql){        //!q.empty()
  41.         int t = q[ql++];
  42.         for(int i = 0; i < n; i++){
  43.             if(m[t *n+ i] && (vis[i] == -1 || vis[i] > vis[t] + m[t *n+ i])){
  44.                 std::cout << "|" << i << " ";
  45.                 q[qr++] = i;
  46.                 vis[i] = m[t *n+ i] + vis[t];
  47.                 restore[i] = t;
  48.             }
  49.         }std::cout << std::endl;
  50.     }
  51.  
  52. exit:   if(vis[finish] == -1)
  53.         return 0;
  54.     else{
  55.         int *p = new int[n+1];
  56.         int r = finish;
  57.         p[0] = 1;
  58.         p[1] = finish;
  59.         do{
  60.             r = restore[r];
  61.             p[++p[0]] = r;
  62.         }while(p[p[0]] != start);
  63.         //for(int i = 1; i <= p[0]; i++) std::cout << p[i] << " ";
  64.         return p;
  65.     }
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement