Advertisement
Guest User

dfs_one_way

a guest
Oct 31st, 2014
146
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.71 KB | None | 0 0
  1. #include <iostream>
  2. #include <deque>
  3. #include <algorithm>
  4. #include <vector>
  5. #include <vector>
  6. #include <fstream>
  7. #include <ctime>
  8.  
  9. using namespace std;
  10.  
  11. bool m[100][100];
  12. bool used[100];
  13. deque<int>best_path;
  14. deque<int>path;
  15. bool done = false;
  16.  
  17. void dfs(int i, int to, int n){
  18.     used[i] = true;
  19.     path.push_back(i);
  20.     if(i == to){
  21.         best_path = path;
  22.         done = true;
  23.     }
  24.     else {
  25.         for(int j = 0; j<n; j++){
  26.             if(m[i][j] && !used[j] && !done){
  27.                 dfs(j,to,n);
  28.             }
  29.         }
  30.     }
  31.     path.pop_back();
  32. }
  33.  
  34. ostream& operator<<(ostream& os, vector<int>a){
  35.     for(int i = 0; i<a.size(); i++){
  36.         os<<a[i]<<" ";
  37.     }
  38.     return os;
  39. }
  40.  
  41. ostream& operator<<(ostream& os, deque<int>a){
  42.     for(int i = 0; i<a.size(); i++){
  43.         os<<a[i]<<" ";
  44.     }
  45.     return os;
  46. }
  47.  
  48. int main()
  49. {
  50.     //string s = "D://Studying/C/Tools/QtCreator/bin/dfs/test.txt";
  51.     string s = "D://Shmyginds/for_c++/olympy/test.txt";
  52.     ifstream fin(s.c_str());
  53.     int n;
  54.  
  55.     int from, to;
  56.     cin>>n>>from>>to;
  57.     for(int i = 0; i<n; i++){
  58.         used[i] = false;
  59.         for(int j = 0; j<n; j++){
  60.             m[i][j] = false;
  61.         }
  62.     }
  63.     for(int i = 0; i<n; i++){
  64.         for(int j = 0; j<n; j++){
  65.             fin>>m[i][j];
  66.             cout<<m[i][j]<<" ";
  67.             //cin>>m[i][j];
  68.         }
  69.         cout<<endl;
  70.     }
  71.     dfs(from-1, to-1, n);
  72.     int steps;
  73.     if(best_path.size()>0){
  74.         steps = best_path.size()-1;
  75.         for(int i = 0; i<best_path.size(); i++){
  76.             best_path[i]++;
  77.         }
  78.         cout<<steps<<endl;
  79.         cout<<best_path;
  80.     }
  81.     else{
  82.         cout<<-1;
  83.     }
  84.     return 0;
  85. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement