问题描述
n个同学分n本书,每个人都有自己喜欢的书(即a[i][j]==1),求出所有的分配方案
#include<iostream>
#include<string>
using namespace std;
string name[25];//n个学生的名字 ,用于读入
int c,n;//c记录可能的情况的个数,用于输出
int flag[25],book[25],a[25][25];//flag记录第i本书是否被分,book记录第i个学生分到的书,a数组如题
void printx(){
cout<<"answer"<<c<<":"<<endl;
for (int i=1;i<n;i++){
char ch=64+book[i];
cout<<name[i]<<":"<<ch<<endl;
}
}//输出第c种可能的情况
void tried(int step){
if (step==n+1){
printx();
return;
}//所有人都分配过了就输出这种情况
for(int i=1;i<=n;i++){
if(a[step][i]==1&&flag[i]==0){//第step个人对第i本书有兴趣,且第i本书没被分
flag[i]=1;
book[step]=i;//记录
tried(step+1);//递归
flag[i]=0;
book[step]=0;//回溯
}
}
}
int main(){
cin>>n;
for(int i=1;i<=n;i++)
flag[i]=0;//初始化flag数组,要养成这个习惯
for(int i=1;i<=n;i++)
cin>>name[i];//输入学生姓名
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
tried(1);//从第一个学生开始分书
return 0;
}
网友评论