题目大意:给出一串字符串,问这串字符串是不是回文字符串,如果是的话需要移动几步
解题思路:判断是不是回文,只需要判断里面的字母的个数,如果奇数字符出现超过了1个,那个这个就不是回文字符串了。接下来是移动,应该由外向里移动,不管是先移动那个字符,最后移动的步数都是一样的,所以从前往后扫描,判断一下最短的移动距离,然后移动,每移动一个,count++
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
const int maxn = 100 + 5;
char str[maxn];
int judge[28],vis[maxn],len,count,test;
bool flag;
int main() {
scanf("%d", &test);
getchar();
while(test--) {
count = 0,flag = false;
scanf("%s",str);
len = strlen(str);
memset(judge,0,sizeof(judge));
for(int i = 0 ; i < len ; i++) {
judge[str[i]-'a']++;
}
for(int i = 0; i < 26; i++)
if(judge[i] % 2 != 0) {
count++;
if(count > 1) {
flag = true;
break;
}
}
if(flag){
printf("Impossible\n");
continue;
}
else {
int left = 0, right = len - 1, cnt = 0;
while(left < right) {
int lcur = left, rcur = right, temp , Min = 0x3f3f3f3f;
memset(vis,0,sizeof(vis));
for(int i = left ; i < right; i++)
if(!vis[i]) {
vis[i] = 1;
int lastcur = i;
for(int j = i + 1; j <= right; j++)
if(str[i] == str[j]) {
vis[j] = 1;
lastcur = j;
}
temp = i - left + right - lastcur;
if(temp < Min) {
Min = temp;
lcur = i;
rcur = lastcur;
}
}
for(int i = lcur; i > left; i--) {
swap(str[i],str[i-1]);
cnt++;
}
for(int i = rcur; i < right; i++) {
swap(str[i],str[i+1]);
cnt++;
}
left++;
right--;
}
printf("%d\n",cnt);
}
}
return 0;
}