[回溯法] 和尚挑水問題-華為筆試

某寺廟裡7個和尚:輪流挑水，為了和其他任務不能沖突，各人将有空天數列出如下表：
和尚1: 星期二,四;
和尚2: 星期一,六;
和尚3: 星期三,日;
和尚4: 星期五;
和尚5: 星期一,四,六;
和尚6: 星期二,五;
和尚7: 星期三,六,日;
請将所有合理的挑水時間安排表 。
           

#include <iostream>
using namespace std;
struct st
{
    int isFree[7];   //和尚某天是否空閑（1為空閑）
    bool haveWorked; //在一次解法中是否挑過水（1為挑過水）
}monk[7];

int sum;       //方案總數
int x[7]={0};  //具體方案數組，1表示挑水，0表示不挑水

void backtrack(int n)
{
    int i=0;
    if(n==7)   //得到一組解并輸出
    {
        sum++;
        cout<<"第"<<sum<<"種方案："<<endl;
        for(i=0;i<7;i++)
            cout<<x[i]<<' ';
        cout<<endl;
    }
    else
    {
        for(i=1;i<=7;++i)
        {
            if(monk[i-1].isFree[n]==1&&monk[i-1].haveWorked==false) //和尚i沒有挑過水且在星期n有時間
            {
                x[n]=i;
                monk[i-1].haveWorked=true;
                backtrack(n+1);
                monk[i-1].haveWorked=false;
            }
        }
    }
}
int main()
{
    int b[7][7]={{1,0,0,1,0,1,0},{0,0,1,1,0,0,0},{0,1,0,0,1,0,1},{1,1,0,0,0,1,0},\
             {0,0,1,0,1,0,0},{0,0,0,1,0,0,1},{1,0,0,0,1,0,0}};
    int i,j;
    for(i=0;i<7;++i)    //狀态初始化
    {
        for(j=0;j<7;++j)
            monk[i].isFree[j]=b[i][j];
        monk[i].haveWorked=false;
    }
    backtrack(0);
    return 0;
}