大致思路
按照题意,每次只能操作相邻的两个砖块,有n-1种操作。将相邻的两个砖块翻转两次等同于没有翻转。所以只要保证遍历一次后最后一个砖块为目标砖块,即可以在3n次操作内完成目标。
==例如:第i个砖块为'W',而目标砖块c为'B'。于是将i和i+1位置的砖块颜色分别反转。==
代码实现
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int n;
string str,args; //args:临时字符串
vector<int> res;
void change(int loc){
if(args[loc]=='W') args[loc]='B';
else args[loc]='W';
}
bool invert(string str,char c){ //判断砖块是否能全部翻转成颜色c
res.clear(); //初始化答案容器
args=str;
for(int i=0;i<args.size()-1;i++){
if(args[i]!=c){
change(i);
change(i+1);
res.push_back(i); //记录每次操作的位置
}
}
if(args.back()!=c) return false;
cout<<res.size()<<endl;
if(res.size()){
for(auto reg:res){
cout<<reg+1<<" ";
}
cout<<endl;
}
return true;
}
int main()
{
int t;
cin>>t;
while(t--){
cin>>n;
cin>>str; //原字符串
if(!invert(str,'W')&&!invert(str,'B')) cout<<-1<<endl;
}
return 0;
}