c++ 深度优先搜索算法

2017-01-12 09:53:06来源:oschina作者:元禛慎独人点击

深度优先搜索


有A、B、C、D、E5本书,要分给张、王、刘、赵、钱5位同学,每人只能选1本。每个人都将自己喜爱的书填写在下表中。请你设计一个程序,打印出让每个人都满意的所有分书方案。



#######################################################


yuanzhen@ubuntu:~/C_script$ cat dfs_one.cpp #include #include #include #include


using std::cout; using std::endl; using std::vector; using std::set;


typedef vector > VECTOR_VEC_INT;


VECTOR_VEC_INT vec; //VECTOR_VEC_INT book(5,vector(5,0)); vector book(5,0); vector person(5,0); set > pset;


void show(VECTOR_VEC_INT avec) { VECTOR_VEC_INT::const_iterator cit; vector::const_iterator it;


for(cit=avec.begin(); cit!=avec.end();++cit) { vector bvec=(*cit); for(it=bvec.begin();it!=bvec.end();++it) {cout << *it << " "; } cout << endl; } }


VECTOR_VEC_INT init() { VECTOR_VEC_INT avec(5,vector(5,0)); //show(avec); avec[0][2]=1; avec[0][3]=1; avec[1][0]=1; avec[1][1]=1; avec[1][4]=1; avec[2][1]=1; avec[2][2]=1; avec[3][3]=1; avec[4][1]=1; avec[4][4]=1; return avec; }


void show_book(vector book, const char* bstr) { cout << bstr << "/t"; for(int i=0;i

void dfs(int step) { if(step==5) { set >::iterator it; it=pset.find(person); if(vec[0][person[0]]==1 && vec[1][person[1]]==1 && vec[2][person[2]]==1 && vec[3][person[3]]==1 && vec[4][person[4]]==1 && it==pset.end()) {pset.insert(person);for(int i=0;i

for(int p=0;p<5;p++){for(int b=0;b<5;b++){if(vec[p][b]==1 && book[b]==0 && person[p]==0){ book[b]=1; person[p]=b; //cout << step << "/t"; //show_book(person,"person1"); dfs(step+1); book[b]=0; person[p]=0; //cout << step << "/t"; //show_book(person,"person2");}}} } }


int main(int argc, char** argv) { vec=init(); show(vec); cout << "-----------------------" << endl; dfs(1);


}


################################################


在代码中,使用了set,因为若不是set 就会出现 重复输出的情况,清楚原因。希望有知道的大侠予以指正

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台