首页 > ACM题库 > HDU-杭电 > HDU 4162-Shape Number-字符串-[解题报告]HOJ
2015
05-23

HDU 4162-Shape Number-字符串-[解题报告]HOJ

Shape Number

问题描述 :

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).
Iterated Difference

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.

输入:

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.

输出:

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.

样例输入:

22234446466001207560
12075602223444646600

样例输出:

00110026202011676122
00110026202011676122

小记:这题题意看的有点麻烦,但是读懂了就简单多了。差分链码出了一次错…

思路:如果仅仅只是求最小的字母序的排列,那么就可以直接用字符串的最小表示法直接解决,可以得到最小排列的第一个字符在该字符串的那个位置。

但是题目要求了,必须要规范normalize。 所以要求一阶差分链码,求了一阶差分链码之后,然后对这链码用最小表示法直接求解。

循环字符串的最小表示法的问题可以这样描述:

对于一个字符串S,求S的循环的同构字符串S’中字典序最小的一个。

就是对于一个字符串s,设两个变量i, j, 分别指向该字符串的第一个和第二个,即i=0,j=1,然后一起往后比对,假设往后已经比对了k个字符,

如果s[i+k] == s[j+k] 那么k++,往后继续比对

如果s[i+k] > s[j+k],那么 我们就要移动i的位置,使得i = i+k+1

如果s[i+k] < s[j+k] ,那么我们就要移动j的位置, 使得 j = j+k+1

如果i == j就让 j++

同时如果s[i+k] != s[j+k] 那么 k就要置0

最后返回 i<j?i:j 即可

这里还有个问题,就是一阶差分链码,一阶差分链码必须是 s[i] = s[i+1] – s[i],  但是这样s[i]就可能不在[0,7]的范围呢,于是因为循环的原因要这样写

s[i] = (s[i+1] -s[i] + 8)%8;

之前我写的是绝对值,所以wa了一次

代码:

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

#define mst(a,b) memset(a,b,sizeof(a))
#define REP(a,b,c) for(int a = b; a < c; ++a)
#define eps 10e-8
#define MAX 10

const int MAX_ = 100010;
const int N = 500000;
const int INF = 0x7fffffff;

char str[MAX_], str1[MAX_];


int Minimze(char s[])
{
    int i, j, len, k;
    i = 0; j = 1; len = strlen(s); k = 0;
    while(i < len && j < len && k < len){
        int t = s[(i+k)%len] - s[(j+k)%len];
        if(!t)++k;
        else {
            if(t > 0)i = i+k+1;
            else j = j + k +1;
            if(i == j)++j;
            k = 0;
        }
    }
    return i>j?j:i;
}

int main() {
    int T, n, m, numa = 0, numb = 0,ans;
    bool flag = 0;
    string s = "";



    while(~scanf("%s", str)) {
        int len = strlen(str);
        REP(i, 1, len+1){
            str1[i-1] = (str[i%len] - str[i-1] + 8)%8+'0';
        }
        str1[len] = '\0';
        ans = Minimze(str1);
        REP(i, 0, len){
            printf("%c", str1[(ans+i)%len] );
        }
        putchar('\n');

    }
    return 0;
}


版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ljd4305/article/details/38116909