希望的海洋

Ain't about how fast I get there,ain't about what's waiting on the other side

常用链接

统计

最新评论

usaco_clocks dfs/bfs/位运算

The Clocks
IOI'94 - Day 2
Consider nine clocks arranged in a 3x3 array thusly: 
|-------| |-------| |-------| | | | | | | | |---O | |---O | | O | | | | | | | |-------| |-------| |-------| A B C |-------| |-------| |-------| | | | | | | | O | | O | | O | | | | | | | | | | |-------| |-------| |-------| D E F |-------| |-------| |-------| | | | | | | | O | | O---| | O | | | | | | | | | |-------| |-------| |-------| G H I

The goal is to find a minimal sequence of moves to return all the dials to 12 o'clock. Nine different ways to turn the dials on the clocks are supplied via a table below; each way is called a move. Select for each move a number 1 through 9 which will cause the dials of the affected clocks (see next table) to be turned 90 degrees clockwise.

Move Affected clocks
1 ABDE
2 ABC
3 BCEF
4 ADG
5 BDEFH
6 CFI
7 DEGH
8 GHI
9 EFHI

Example

Each number represents a time accoring to following table: 
9 9 12 9 12 12 9 12 12 12 12 12 12 12 12 6 6 6 5 -> 9 9 9 8-> 9 9 9 4 -> 12 9 9 9-> 12 12 12 6 3 6 6 6 6 9 9 9 12 9 9 12 12 12

[But this might or might not be the `correct' answer; see below.]

PROGRAM NAME: clocks

INPUT FORMAT

Lines 1-3: Three lines of three space-separated numbers; each number represents the start time of one clock, 3, 6, 9, or 12. The ordering of the numbers corresponds to the first example above.

SAMPLE INPUT (file clocks.in)

9 9 12 6 6 6 6 3 6

OUTPUT FORMAT

A single line that contains a space separated list of the shortest sequence of moves (designated by numbers) which returns all the clocks to 12:00. If there is more than one solution, print the one which gives the lowest number when the moves are concatenated (e.g., 5 2 4 6 < 9 3 1 1).

SAMPLE OUTPUT (file clocks.out)

4 5 8 9

    不算太难的搜索题，由于题目要求步数最少，所以很容易想到广搜。但分析题目发现一些可剪枝的地方：

        1、任何一种步骤使用4次相当于没有使用；

        2、步骤使用的先后顺序不会影响最终结果；

    这样，最终使用的总步骤数不会超过3*9=27步。所以深搜显得更直接简单而且耗费内存很小。而且由性质2我们可以在搜索的时候每次只试序号大于等于上一次用的步骤的序号的步骤。

    当然这个题用广搜也是可以解决的，这里提供深搜和广搜的源码。

    广搜源码如下：

#include <fstream>

using namespace std;

const int with[10][5]={{},{1,2,4,5},{1,2,3},{2,3,5,6},{1,4,7},{2,4,5,6,8},{3,6,9},{4,5,7,8},{7,8,9},{5,6,8,9}};
char t[270000][10],way[270000]={1},use[270000][10];
int pre[270000];
string ans;

void bfs();
bool check(int);
void work(int,int,int);

int main() {
    ifstream fin ("clocks.in");
    ofstream fout ("clocks.out");
    for (int i=1,tem;i<=9;i++) {
        fin >> tem;
        t[0][i]=tem%12;
    }
    bfs();
    fout << ans << endl;
    fin.close();
    fout.close();
    return 0;
}

void bfs() {
    int tail=0,head=-1;
    while (tail>head) {
        head++;
        for (int i=way[head];i<=9;i++) if (use[head][i]<3){
            work(i,head,++tail);
            way[tail]=i;
            pre[tail]=head;
            for (int j=1;j<=9;j++) use[tail][j]=use[head][j];
            use[tail][i]++;
            if (check(tail)) {
                ans=char(way[tail]+'0');
                for (int j=pre[tail];j!=0;j=pre[j]) {
                    ans=' '+ans;
                    ans=char(way[j]+'0')+ans;
                }
                return;
            }
        }
    }
}

bool check(int k) {
    for (int i=1;i<=9;i++) if (t[k][i]!=0) return false;
    return true;
}

void work(int k,int from,int cur) {
    for (int i=1;i<=9;i++) t[cur][i]=t[from][i];
    for (int i=0;i<=4 && with[k][i]!=0;i++) t[cur][with[k][i]]=(t[from][with[k

/*
ID:greenwo1
PROG: clocks
LANG:C++
*/
#include<cstdio>
#include<cstdlib>
#include<string>
//#include<cmath>
//#include<algorithm>
//#include<queue>
#include<iostream>
using namespace std;
int slu[100],way[100],cur[9],used[9];//hulue 3*9ci maximum times

int mini=1000000;
//int move[9]={110110000,111000000,011011000,100100100,
//010111010,001001001,000110110,000000111,000011011};

int move[9]={110110000,111000000,11011000,100100100,
10111010,1001001,110110,111,11011};
bool judge(int* arr)
{
    int i;
    for(i=0;i<9;i++)
        if(*(arr+i)!=12)return 0;
    return 1;
}

int convert(int k)
{
    if(k/10)
        return k%10+2*convert(k/10);
    else return k%10;
}
void dfs(int* path,int m,int t)
{
    int i,j,k;
    if(m>mini||m>27)return;
    /*if(m==27)
    printf("dfs:%d\n",m);*/
    if(judge(cur))
    {
        if(m<mini)
        {
            mini=m;
            //memcpy(way,slu,mini*sizeof(int));
            for(i=0;i<mini;++i)
                way[i]=slu[i];
        }
        return ;
    }
    
    for(i=t;i<9;i++)
    {
        if(used[i]>=3)continue;
        if(used[i]<3)
        {
        
            *(path)=i;
            k=move[i];
            used[i]++;
            //printf("dfs:%d %d %d\n",m,i,used[i]);
            for(j=0;j<9;j++)
            {
                if(k&1<<(8-j))cur[j]=(cur[j]+3);
                if(cur[j]>12)cur[j]-=12;
            }
            dfs(path+1,m+1,i);
            for(j=0;j<9;j++)
            {
                if(k&1<<(8-j))cur[j]=(cur[j]-3);
                if(cur[j]<=0)cur[j]+=12;
            }
            used[i]--;
        }
    }

}
int main()
{
    int i,j,k,n;
    FILE* fin,*fout;
    fin=fopen("clocks.in","r");
    fout=fopen("clocks.out","w");

    for(i=0;i<9;i++)
    {
        move[i]=convert(move[i]);
    }
    for(i=0;i<9;++i)
      fscanf(fin,"%d",&cur[i]);
    for(i=0;i<9;i++)
    {
            slu[0]=i;
            k=move[i];
            used[i]++;
            //printf("dfs:%d %d %d\n",m,i,used[i]);
            for(j=0;j<9;j++)
            {
                if(k&1<<(8-j))cur[j]=(cur[j]+3);
                if(cur[j]>12)cur[j]-=12;
            }
            dfs(slu+1,1,i);
            for(j=0;j<9;j++)
            {
                if(k&1<<(8-j))cur[j]=(cur[j]-3);
                if(cur[j]<=0)cur[j]+=12;
            }
            used[i]--;
    }
    //printf("%d\n",mini);
    fprintf(fout,"%d",way[0]+1);
    for(k=1;k<mini;k++)fprintf(fout," %d",way[k]+1);
    fprintf(fout,"\n");
        return 0;
}

][i]]+3)%12;
}

posted on 2011-09-13 11:40 拥梦的小鱼 阅读(344) 评论(0)  编辑 收藏 引用 所属分类: USACO


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理