Tobo or not Tobo

Time Limit : 2000/1000ms (Java/Other)   Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 2   Accepted Submission(s) : 1

The game of Tobo is played on a plastic board designed into a 3 × 3 grid with cells numbered from 1 to 9 as shown in figure (a). The grid has four dials (labeled ``A" to ``D" in the figure.) Each dial can be rotated in 90 degrees increment in either direction. Rotating a dial causes the four cells currently adjacent to it to rotate along. For example, figure (b) shows the Tobo after rotating dial ``A" once in a clockwise direction. Figure (c) shows the Tobo in figure (b) after rotating dial ``D" once in a counterclockwise direction. 




Kids love to challenge each other playing the Tobo. Starting with the arrangement shown in figure (a), (which we‘ll call the standard arrangement,) one kid would randomly rotate the dials, X number of times, in order to ``shuffle" the board. Another kid then tries to bring the board back to its standard arrangement, taking no more than X rotations to do so. The less rotations are needed to restore it, the better. This is where you see a business opportunity. You would like to sell these kids a program to advise them on the minimum number of steps needed to bring a Tobo back to its standard arrangement.

3413569728
1165432789
0000000000

1. 2
2. -1

IDA*

预估值  曼哈顿距离

剪枝  上一层A点顺时针转  下一层则不必要A点逆时针转

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <string>

using namespace std;

int dir[4][4]= {{3,0,4,1},{4,1,5,2},{6,3,7,4},{7,4,8,5}};
int ddir[4][4]= {0,1,3,4,1,2,4,5,3,4,6,7,4,5,7,8};
char str[20];

int abs(int n)
{
    if(n<0) return 0-n;
    return n;
}

int get_h(int a[3][3])
{
    int ans=0;
    for(int i=0; i<3; i++)
    {
        for(int j=0; j<3; j++)
        {
            ans+=abs(i-(a[i][j]-1)/3)+abs(j-(a[i][j]-1)%3);
        }
    }
    return (ans+3)/4;
}

bool dfs(int len,int a[3][3],int kind,int kind2)
{
    if(len<get_h(a))
        return false ;
    if(len==0)
        return true ;
    for(int i=0; i<4; i++)
    {
        int aa[3][3];
        for(int j=0; j<3; j++)
            for(int k=0; k<3; k++)
                aa[j][k]=a[j][k];
        if(!(kind==i&&kind2==2))//剪枝  防止转回上一层状态
        {
            for(int j=0; j<4; j++)
                aa[ddir[i][j]/3][ddir[i][j]%3]=a[dir[i][j]/3][dir[i][j]%3];

            if(dfs(len-1,aa,i,1)) return true ;
        }
        if(kind==i&&kind2==1) continue ;
        for(int j=0; j<4; j++)
            aa[dir[i][j]/3][dir[i][j]%3]=a[ddir[i][j]/3][ddir[i][j]%3];

        if(dfs(len-1,aa,i,2)) return true ;
    }
    return false ;
}

int main()
{
    int tt=1;
    while(~scanf("%s",str)&&strcmp(str,"0000000000"))
    {
        printf("%d. ",tt++);
        int Map[3][3];
        for(int i=1; i<10; i++)
            Map[(i-1)/3][(i-1)%3]=str[i]-'0';
        int len,length=str[0]-'0';
        for(len=get_h(Map); len<=length; len++)
        {
            if(dfs(len,Map,-1,-1))
            {
                printf("%d\n",len);
                break;
            }
        }
        if(len>length) printf("-1\n");
    }
    return 0;
}

HDU 2918 Tobo or not Tobo

原文：http://blog.csdn.net/u013097262/article/details/49721703