程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 2918 Tobo or not Tobo

HDU 2918 Tobo or not Tobo

編輯:關於C++

 

Tobo or not Tobo

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)
Total Submission(s) : 2 Accepted Submission(s) : 1
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

 

IDA*

 

預估值 曼哈頓距離

剪枝 上一層A點順時針轉 下一層則不必要A點逆時針轉

 

 

#include 
#include 
#include 
#include 
#include 

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(lenlength) printf(-1
);
    }
    return 0;
}


 

 

 

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved