Tobo or not Tobo

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1062 Accepted Submission(s): 418

Problem Description 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.
Input Your program will be tested on one or more test cases. Each test case is specified on a line by itself. Each line is made of 10 decimal digits. Let's call the first digit Y . The remaining 9 digits are non-zeros and describe the current arrangement of the Tobo in a row-major top-down, left-to-right ordering. The first sample case corresponds to figure (c).

The last line of the input file is a sequence of 10 zeros.
Output For each test case, print the result using the following format:


k . R


where k is the test case number (starting at 1,) is a single space, and R is the minimum number of rotations needed to bring the Tobo back to its standard arrangement. If this can't be done in Y dials or less, then R = -1.
Sample Input

3413569728
1165432789
0000000000

Sample Output

1. 2
2. -1

Source 2008 ANARC
Recommend lcy | We have carefully selected several similar problems for you: 2926 2924 2923 2925 2922
題目大意：具體沒怎麼讀題，AC的猜測是這樣的：有A、B、C、D四個按鍵，按下一次可以順時針或逆時針旋轉90度，變成對應的樣子。最後要求輸出所給的序列變成目標序列123456789最少需要移動幾步。 特別注意： 1、輸入的第一個數字為最多的步數，如果在所規定的步數內沒有完成就直接輸出-1。 2、每次最多移動四個數字，所以get_h()的最優解即為：（最少不在正確位置的字符數+3）/4。 3、最後注意輸出的格式，避免PE。
詳見代碼。

#include 
#include 
#include 
#include 

using namespace std;

char ch[20];
char str[10][10],Map[10][10];
int want;

void init()
{
    char g='1';
    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
        {
            Map[i][j]=g++;
        }
    }
}


void move_c(int i,int j)//順時針旋轉
{
    char t=str[i][j];
    str[i][j]=str[i+1][j];
    str[i+1][j]=str[i+1][j+1];
    str[i+1][j+1]=str[i][j+1];
    str[i][j+1]=t;
}

void move_e(int i,int j)//逆時針旋轉
{
    char t=str[i][j];
    str[i][j]=str[i][j+1];
    str[i][j+1]=str[i+1][j+1];
    str[i+1][j+1]=str[i+1][j];
    str[i+1][j]=t;
}

int get_h()
{
    init();
    int t=0;
    int ans=0;
    for (int i=0; i<3; i++)//查找最少有多少個字符不在正確的位置上
    {
        for (int j=0; j<3; j++)
        {
            if (str[i][j]!=Map[i][j])
                t++;
        }
    }
    ans=(t+3)/4;//ans表示的是最少錯誤字符需要走的步數
    return ans;
}

bool IDA(int dep)//傳過的值為已經走了的步數
{
    if (dep+get_h()>want)
        return false;
    //cout<<    <kk)//在規定的步數內不能實現
            {
                flag=0;
                break;
            }
        }
        if (flag==1)
            printf (%d. %d
,Case++,want);
        else
            printf (%d. -1
,Case++);
    }
    return 0;
}