POJ_1256 Anagram
勉強する気がおきない。
問題
単語が与えられる。辞書式配列で、並び替えたものをすべて列挙せよ。
重複はだめ。
解法
やるだけ。
辞書の順序が
AaBbCc...Zzとなっているのでこれに注意し、文字<->数値の変換用配列を作っておくと便利。
重複がダメなので、使った文字を覚えておかないといけない。
実装
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAX_STRLEN = 100; int a2i[128]; char i2a[26 * 2]; char string[MAX_STRLEN];//文字列 int s_len; //文字列長 bool used[MAX_STRLEN]; //文字を使用したかのフラグ void init(){ for(int i = 0; ; i++){ a2i['A' + i] = i * 2; i2a[i * 2] = 'A' + i; a2i['a' + i] = i * 2 + 1; i2a[i * 2 + 1] = 'a' + i; if('A' + i == 'Z') break; } } char anagram[MAX_STRLEN]; void g(int n){ if(n == s_len){ anagram[n] = 0; printf("%s\n", anagram); return; } bool used_num[26 * 2]; //同じ文字列を重複して作らないため fill(used_num, used_num + 26 * 2, false); for(int i = 0; i < s_len; i++){ if(used_num[string[i]] || used[i]) continue; used_num[string[i]] = true; used[i] = true; anagram[n] = i2a[string[i]]; g(n + 1); used[i] = false; } } int main(){ int n; char c; init(); scanf("%d", &n); for(int i = 0; i < n; i++){ scanf("%s", string); scanf("%c", &c); s_len = strlen(string); for(int j = 0; j < s_len; j++) string[j] = a2i[string[j]]; sort(string, string + s_len); fill(used, used + MAX_STRLEN, false); g(0); } return 0; }