[USACO][Section 1.4][搜索] The Clocks

题目大意：

给出9个表盘和9种表针操作方法，要求找出一个能使所有表针都指向12点的方案。

思路：

用深搜遍历所有可能方案即可，具体思路见代码。

代码：

/*
ID: lujunda1
LANG: C++
PROG: clocks
*/
#include
#include
#include
#include
#include
using namespace std;
struct state
//定义结构体来表示当前时钟的状态。mark[]记录各方法使用的数量。 
{
    int clock[3][3];
    int mark[9];
};
bool check(state temp)
//通过temp的clock[]判断temp状态下的表针是否全部指向12点。 
{
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            if(temp.clock[i][j]%12)
                return false;
    return true;
}
void output(state temp)
//输出temp状态下的方法序列。 
{
    bool check=true;
    for(int i=0;i<9;i++)
        for(int j=0;j=0;i--)
    //返回使用次数不为0且序号最大的方法的序号。 
        if(temp.mark[i]>0)
            return i;
    return 0;
}
bool dfs(state temp)
//深搜 
{
    if(check(temp))
    //优先检查temp状态 
    {
        output(temp);
        return true;
    }
    for(int i=pos(temp);i<9;i++) 
        if(temp.mark[i]<3&&dfs(op(temp,i)))
        //temp.mark[i]<3保证了每个方法使用不超过4次，超过4次无意义（指针转了超过一圈）。 
            return true;
    return false;
}
int main()
{
    freopen("clocks.in","r",stdin);
    freopen("clocks.out","w",stdout);
    state original;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            scanf("%d",&original.clock[i][j]);
    for(int i=0;i<9;i++)
        original.mark[i]=0;
    dfs(original);
}

发表回复取消回复