HDU 4162 Shape Number(最小表示法)

題目連結：http://acm.hdu.edu.cn/showproblem.php?pid=4162

Shape Number

Time Limit: 24000/12000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 841    Accepted Submission(s): 405

Problem Description In computer vision, a chain code is a sequence of numbers representing directions when following the contour of an object. For example, the following figure shows the contour represented by the chain code 22234446466001207560 (starting at the upper-left corner).

Two chain codes may represent the same shape if the shape has been rotated, or if a different starting point is chosen for the contour. To normalize the code for rotation, we can compute the first difference of the chain code instead. The first difference is obtained by counting the number of direction changes in counterclockwise direction between consecutive elements in the chain code (the last element is consecutive with the first one). In the above code, the first difference is

00110026202011676122

Finally, to normalize for the starting point, we consider all cyclic rotations of the first difference and choose among them the lexicographically smallest such code. The resulting code is called the shape number.

00110026202011676122

01100262020116761220

11002620201167612200

...

20011002620201167612

In this case, 00110026202011676122 is the shape number of the shape above.  

Input The input consists of a number of cases. The input of each case is given in one line, consisting of a chain code of a shape. The length of the chain code is at most 300,000, and all digits in the code are between 0 and 7 inclusive. The contour may intersect itself and needs not trace back to the starting point.  

Output For each case, print the resulting shape number after the normalizations discussed above are performed.  

Sample Input

22234446466001207560
12075602223444646600
        

Sample Output

00110026202011676122
00110026202011676122
        

大概意思就是：如果目前數字後面一個數大于目前數，目前數等于下一個數減去目前數；反之則下一個數+8減去目前數（if(a[i+1]>a[i])  a[i]=a[i+1]-a[i];    else  a[i] = a[i+1]+2-a[i]）  ,再利用最小表示法得出結果字元串

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define min(a,b) a<b? a:b
int min_show(char *s)
{
    int x,y,i=0,j=1,k=0,len=strlen(s);

    while(i<len&&j<len&&k<len)
    {
        x=(i+k)%len;
        y=(j+k)%len;
        if(s[x]>s[y])  //當x下标的比y下标的大，則移i；
            i=i+k+1,k=0;
        else if(s[x]<s[y])
            j=j+k+1,k=0;  //k代表跳的步數
        else    //如果相等，則計算出i,j的位置差，減少計算步驟
            k++;
        if(i==j) j++;
    }
    return min(i,j);
}


int main()
{
    char str[300100];
    char temp[300100];

    while(scanf("%s",str)!=EOF)
    {
        int k = strlen(str);

        int i;
        for(i=0; i<k; i++)
        {
            if(i==k-1)
            {
                if(str[0]>=str[i])
                    temp[i]=str[0]-str[i]+48;
                else
                    temp[i]=str[0]+8-str[i]+48;

            }
            else
            {
                if(str[i+1]>=str[i])
                    temp[i]=str[i+1]-str[i]+48;
                else
                    temp[i]=str[i+1]+8-str[i]+48;

            }

        }
        temp[k]='\0';
       // printf("%s\n",temp);

        int index = min_show(temp);

        for(i=index;i<k;i++)
            printf("%c",temp[i]);
        for(i=0;i<index;i++)
            printf("%c",temp[i]);
        printf("\n");
    }
    return 0;
}