排球队员站位问题+回溯思想

这个题的题意如图所示：

一开始理解起来可能有点困难，但是多看两遍就可以了.......仔细看下题目的每一个要求，这个对解题有很大影响！

思路：这个题，不能全说是搜索，还含有模拟，但是确实少不了搜索这一过程！

这个题采用了回溯的思想，然后就是注意一下3.4号球员是不能在同一排的，而且3号在前排的话只能是在第四号位！其余的应该就没什么了，当然细节也是要注意的嘛！

因为只有一组结果，所以把结果也放出来吧！

代码如下：

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int pos_can_stand[6][6];//表示队员i能否站在位置j，1表示能，0表示不能！
bool pos_can_use[6];//表示位置号是否可以使用,true表示没人，可以使用，false表示有人了不可以使用！
int num[6];//表示队员的最终站位！
void init()
{
    for(int i=0; i<6; i++)
        for(int j=0; j<6; j++)
            if(i==j)
                pos_can_stand[i][j]=0;
            else
                pos_can_stand[i][j]=1;//因为每一个队员的球衣号码都与他们的站位号不同！
    pos_can_stand[0][4] = 0;//1号队员不在后排
    pos_can_stand[0][5] = 0;//1号队员不在后排
    pos_can_stand[1][4] = 0;//2号队员不是二传手
    pos_can_stand[2][1] = 0;//3号队员不是二传手
    pos_can_stand[2][4] = 0;//3号队员不是二传手
    pos_can_stand[4][2] = 0;//5号队员不是副攻手
    pos_can_stand[4][5] = 0;//5号队员不是副攻手
    pos_can_stand[5][2] = 0;//6号队员不是副攻手
    pos_can_stand[5][0] = 0;//6号队员不能站后排
    pos_can_stand[5][4] = 0;//6号队员不能站后排
    for(int i=0; i<6; i++)
        num[i]=-1;//初始化！
    for(int i=0; i<6; i++)
        pos_can_use[i]=true;
}
void fun()
{
    int sum_num=0,pos;
    while(sum_num<6)
    {
        for(pos=0; pos<6;)
        {
            if(sum_num==3)//如果第四号队员
            {
                if(num[2]==3)//如果3号队员站到了4号位（即唯一的前排可能）,则4号队员应站后排
                {
                    pos_can_stand[3][1]=0;
                    pos_can_stand[3][2]=0;
                    pos_can_stand[3][3]=0;
                }
                else//表明第三号队员是站在后排！也就是说第四号球员只能站在前排了！
                {
                    pos_can_stand[3][0]=0;
                    pos_can_stand[3][4]=0;
                    pos_can_stand[3][5]=0;
                }
            }
            else//如果回溯的话，需要对第四位队员进行恢复，否则会发生错误，因为它的站位限制不固定
            {
                for(int i=0; i<6; i++)
                    if(i!=3)
                        pos_can_stand[3][i]=1;
            }
            if(pos_can_stand[sum_num][pos]&&pos_can_use[pos])
            {
                //如果当前的pos位置是可以使用的并且队员是可以在这个位置上的话
                num[sum_num]=pos;//把pos这个位置给sum_num+1号队员来站！
                pos_can_use[pos]=false;//此位置已经有人了！
                sum_num++;
                break;//退出for循环！
            }
            else
                pos++;//不然寻找下一个位置！
            while(pos==6)//如果找完了所有得位置都没发现能够符合条件，那就回溯！
            {
                sum_num--;//回溯到上一个队员！
                pos=num[sum_num];
                pos_can_use[pos]=true;//此时由于需要重新给sum_num找位置，
                //所以需要把之前使用的位置标记为没人使用！
                num[sum_num]=-1;
                pos++;//然后找下一个位置！
            }
        }
    }
}
void print()
{
    for(int i=0; i<6; i++)
        printf("第[%d]位队员所站的位置是[ %d ]......\n",i+1,num[i]+1);
}
int main()
{
    init();
    fun();
    print();
    return 0;
}

排球队员站位问题+回溯思想

原文：http://blog.csdn.net/u014004096/article/details/40543039