著名医生的药方(回溯剪枝法)

Description

很久以前，有一个医术非常高明的医生，曾经医治好了很多怪病。但是，他开出的药方的字迹却是十分难辨认的，只有他自己和他自己的药剂师才能够读懂他的药方。有时候，甚至是两个不同的药方的同一种药都是难以鉴别出的。
不过，这个医生在开药方的时候，习惯有一个固定的标准模式。他有一个药材库，里面共有n种药，除了这n种药，他不会使用任何其他的药。对于每一种 药，都有一个关于它的后续药的集合，只有这种药的后续药才能够出现在这种药的下一个位置。当然，任何一种药都可能同时是几种药的后续药。
这个医生开出的药方是一个列表的形式。在他的一个药方中，一种药只可能出现一次。更奇怪的是，当他开出一种药盒它的后续药以后，这种药的其他后续药就不可能出现在之后的序列中。
后来，一些书法家和医生共同分析了这个医生的大量的药方，写出了他的所有药的清单。这里我们用n个整数1，2，...，n来依次表示他的n种药。同时，他们分析了每一种药的可能的后续药的药单。
现在，有一个关于这个医生的药方，药方中写有p种药。可惜的是，药方中有一些药并没有具体辨别出。那么，请你写一个程序，帮忙辨别出药方中不确认的药。当然，对于不确定的药方，可能可以构造出多种不同的药方，那么请你找出所有的情况。

Input

输入数据的第一行只有一个正整数 n（0

Output

输出数据的第一行是一个整数m，表示总共可以构造出m种不同的药方。接下来的m行，每行应该有p个数，具体输出每一种情况的药方，中间用一个空格隔开。所有的m行的输出，必须按照整数排序顺序输出。行首行末无空格。

Sample Input

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

Sample Output

2
2 3 5 4
4 3 5 1

Source

#include
#include
#include
#include
using namespace std;
//前面的结果对后产生影响
//同时注意到路径长度给了，层次深度也定了，为n
vector result;
vector >  all;
namespace std
{
    ostream& operator<<(ostream& os,vector > x)    
    {
        cout<        for(int i=0;i        {
            copy(x[i].begin()+1,x[i].end(),ostream_iterator(cout," "));
            cout<        }
    }
}
int visited[500];
int blocked[500];
int count=0;
void search(int **a,int m,int* path,int n)
{
    //终止的基本条件,表示查找成功
    if(n<0) return;
    if(n==0)
    {
        all.push_back(result);    
        return;
    }
    if(*path==0)
    {
        for(int i=1;i<=m;i++)    
             //减枝,一个元素只能访问一次且每个元素只能做一次后继,如果可以作为前一个的后继的话
            if( !visited[i]&& !blocked[i] && a[result.back()][i])
            {
              
              visited[i]=1;
              //将第result.back()行的未访问的后继都禁掉,此后不会再出现了
              for(int j=1;j<=m;j++)
                  if(visited[j]==0 && !blocked[j] && a[result.back()][j]==1)
                blocked[j]=n;
              result.push_back(i);


              search(a,m,path+1,n-1);

              //恢复现场
              //将前一个元素所在行的未访问的元素都放开
              for(int j=1;j<=m;j++)
                  if(blocked[j]==n)
                blocked[j]=0;
              result.pop_back();
              visited[i]=0;
            }
        //此枝无解   
    }else   //已经有指定的值了
    {
        int i=*path;
        if( !visited[i]&& !blocked[i] && a[result.back()][i])
        {
             
              visited[i]=1;
              //将第result.back()行的未访问的后继都禁掉,此后不会再出现了
              for(int j=1;j<=m;j++)
              if(visited[j]==0 && !blocked[j] && a[result.back()][j]==1)
                blocked[j]=n;
              result.push_back(i);


              search(a,m,path+1,n-1);

              //恢复现场
              //将前一个元素所在行的未访问的元素都放开
              for(int j=1;j<=m;j++)
              if(blocked[j]==n)
                blocked[j]=0;
              result.pop_back();
              visited[i]=0;
        }
    }
}
main()
{
/* example:
    int A[6][6]={
        0,2,2,2,2,2,
        0,0,1,0,1,1,
        0,1,0,1,0,0,
        0,0,0,0,0,1,
        0,0,1,1,0,0,
        0,1,1,0,1,0,   
    };
    int path[4]={0,3,0,0};
*/
    int  tmp,m,n;
    string line;
    int word;
    cout<<"请输入矩阵的行数(所有药的总数):";
    //第一次输入一定会留在输入缓冲区中，所以后面一定要cin.get()将其忽略掉
    cin>>m;
    int* A[m+1];
    for(int i=0;i        A[i]=new int[m+1];
    for(int i=1;i    {
        for(int j=1;j            A[i][j]=0;
        A[i][0]=0;
        A[0][i]=2;
    }
    cin.get(); //这一步很重要
    for(int i=1;i<=m;i++)
    {
        cout<<"请输入第"<        getline(cin,line);
            istringstream s(line); //输入流重定向到string对象
            while(s>>word)   //在string对象中读取数字
        {
            A[i][word]=1;
            cout<<"word is:"<        }
    }

    cout<<"请输入此次药的个数：";
    cin>>n;
    int *path = new int[n];
    for(int i=0;i    {
        cin>>tmp;
        path[i]=tmp;
    }
    for(int i=0;i    {
        for(int j=0;j            cout<        cout<    }
    result.push_back(0);
    search(A,m,path,n);
    cout<}