除了排列方式不同,其他都一樣。
要A > a > B > b > ... > Z > z的順序做排列。
所以先排成他要的這種形式再做backtracking。
/* ACM 195 Anagram * mythnc * 2012/01/08 21:33:59 * run time: 0.044 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXCHAR 1000 #define TRUE 1 #define FALSE 0 void sort(char *, int); void backtrack(int); int cmp(const void *a, const void *b); char input[MAXCHAR], output[MAXCHAR]; int visited[MAXCHAR]; int main(void) { scanf("%*d"); while (scanf("%s", &input) == 1) { sort(input, strlen(input)); backtrack(0); } return 0; } /* sort: sort s in alphabetically order: * A > a > B > b > .... > Z > z */ void sort(char *s, int n) { char upper[MAXCHAR], lower[MAXCHAR]; int i, j, k, up, low; for (i = up = low = 0; i < n; i++) if (s[i] >= 'A' && s[i] <= 'Z') upper[up++] = s[i]; else lower[low++] = s[i]; /* sort each array */ qsort(upper, up, sizeof(char), cmp); qsort(lower, low, sizeof(char), cmp); i = j = k = 0; /* copy back to s (in sorted order) */ while (k < low && j < up) if (lower[k] - 'a' + 'A' < upper[j]) s[i++] = lower[k++]; else s[i++] = upper[j++]; while (k < low) s[i++] = lower[k++]; while (j < up) s[i++] = upper[j++]; } /* backtrack: do backtrack to producing answer */ void backtrack(int i) { int j; /* output */ if (input[i] == '\0') { output[i] = '\0'; printf("%s\n", output); return; } /* clear the previous content in output[i] */ output[i] = -1; for (j = 0; input[j] != '\0'; j++) if (!visited[j] && input[j] != output[i]) { visited[j] = TRUE; output[i] = input[j]; backtrack(i + 1); visited[j] = FALSE; } } /* cmp: for qsort() */ int cmp(const void *a, const void *b) { return *(char *)a - *(char *)b; }
沒有留言:
張貼留言