2014华为机试——两个城市之间的最多路径

题目：

代码：

#include<vector>      
#include<iostream>   
using namespace std;  
  
void print(vector<int> &path,int& number){//打印一条路径
	cout<<"路径"<<number<<":";
	for(vector<int>::iterator iter=path.begin();iter!=path.end();iter++)
		cout<<*iter<<"-";
}
void FindPaths(int **p,int dim,int&pathNumber,vector<int>& path,bool* citylabel,int currentcity,int dest)  
{  
   if(currentcity==dest)//当前城市为终点城市  
       {pathNumber++;
         print(path,pathNumber);
		 cout<<dest<<endl;
        return;}//递归终止条件  
   else {
	   citylabel[currentcity]=true;//标志当前城市已经存在搜索路径中(已经使用) 
	   vector<int> nextcity;   
       for(int j=0;j<dim;j++)//遍历所有可能的下一个城市    
		  if(p[currentcity][j]==1&&!citylabel[j])
			  nextcity.push_back(j);  
 
	   if(!nextcity.empty()){
		   path.push_back(currentcity);//递归，遍历所有可能的下一个城市 
		   for(vector<int>::iterator it=nextcity.begin();it!=nextcity.end();it++)    
			   FindPaths(p,dim,pathNumber,path,citylabel,*it,dest);
		   path.pop_back();
	   }
	   citylabel[currentcity]=false;//标志当前城市已经存在搜索路径中(已经使用)
  }  
}
  
int main()  
{  
    int dim,start,dest;//分别代表城市总数，起点城市，终点城市  
    int pathNumber=0;//路径总数 
	vector<int> path;
    cin>>dim>>start>>dest;  
    bool *citylabel=new bool[dim];//某个城市是否已经在搜索路径中使用  
    int **p=new int*[dim];//城市两两之间是否有路到达  
      
 
	vector<int> nextcity;//可能的下一个城市 
    for(int i=0;i<dim;i++)  
	{
		p[i]=new int[dim];  
        citylabel[i]=false;  
        for(int j=0;j<dim;j++)  
		   {cin>>p[i][j];  
            if(i==start&&p[i][j]==1&&j!=start)//可能的第2个城市  
               nextcity.push_back(j);}  
	}  
        
     citylabel[0]=true;//起点设置为已存在于搜索路径中，即已经使用  
	 path.push_back(start);
     for(vector<int>::iterator it=nextcity.begin();it!=nextcity.end();it++)//以可能的第2个城市为基准，遍历    
         FindPaths(p,dim,pathNumber,path,citylabel,*it,dest);  
       
     cout<<"路径总数为"<<pathNumber<<endl;   
     return 0;  
}  

  当输入为：

              6 1 5
              1 0 0 0 1 0
              1 1 1 1 0 0
              0 0 1 0 1 1
              0 0 1 1 0 1
              0 0 0 1 1 1
              0 0 0 0 0 1

        输出为：路径总数为 9

      即下列9种情况：

      1 0 4 3 2 5
      1 0 4 3 5
      1 0 4 5
      1 2 4 3 5
      1 2 4 5
      1 2 5
      1 3 2 5
      1 3 2 4 5
      1 3 5

思想：

       1.简单的递归。设某个城市为当前城市，搜索其所有有路相连的下个城市，并存储至vector中。将当前城市设定为已经使用，遍历vector中存储的下一个城市，此时递归。一旦某个城市的所有可能的下一步方向遍历完，则将该城市设置为未在搜索路径中。

     2.注意递归终止条件的设定。