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
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
char s[20];
int map[15],r,step;
int check(int a[])
{
int i;
for(i = 1; i<=9; i++)
if(a[i] != i)
return 0;
return 1;
}
void swap(int s[],int a,int b,int c,int d)
{
int t=s[a];
s[a]=s[b],s[b]=s[c],s[c]=s[d];
s[d]=t;
}
void work(int a[],int id)
{
if(id==1) swap(a,1,2,5,4);
if(id==2) swap(a,2,3,6,5);
if(id==3) swap(a,4,5,8,7);
if(id==4) swap(a,5,6,9,8);
if(id==5) swap(a,8,9,6,5);
if(id==6) swap(a,7,8,5,4);
if(id==7) swap(a,5,6,3,2);
if(id==8) swap(a,4,5,2,1);
}
int dfs(int a[],int deep)
{
if(check(a))
return 1;
if(deep>=step)
return 0;
for(int i = 1; i<=8; i++)
{
work(a,i);
if(dfs(a,deep+1)) return 1;
work(a,9-i);
}
return 0;
}
int main()
{
int i,j,cas = 1;
while(~scanf("%s",s))
{
if(!strcmp(s,"0000000000"))
break;
r = s[0]-‘0‘;
for(i = 1; i<=9; i++)
map[i] = s[i]-‘0‘;
step = 0;
while(step<=r)
{
if(dfs(map,0))break;
step++;
}
if(step<=r)
printf("%d. %d\n",cas++,step);
else
printf("%d. -1\n",cas++);
}
return 0;
}
HDU2918：Tobo or not Tobo(IDA),布布扣,bubuko.com
HDU2918：Tobo or not Tobo(IDA)
原文：http://blog.csdn.net/libin56842/article/details/23781751
