問題
http://community.topcoder.com/stat?c=problem_statement&pm=8745&rd=12169
１～ｎまでの数字からなる配列が与えられる。
また、ｋ個の連続した数字を逆順に並び変えることができる。
このとき、元の配列を昇順にソートするのに必要な操作回数を求める。
ただし、昇順にソートできない場合はー１を返す。
解き方
メモ化を利用した全探索を行う。
今回はｄｆｓよりキューを利用したｂｆｓの方が効率よく書くことができる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
map<vector<int>,int> m;
queue<vector<int> > q;
class SortingGame {
public:
int fewestMoves(vector<int> board, int k) {
int n=board.size();
m.clear();
m[board]=1;
q.push(board);
while(!q.empty()){
vector<int> cur=q.front();
q.pop();
for(int i=0;i+k<=n;i++){
vector<int> tmp=cur;
reverse(tmp.begin()+i,tmp.begin()+i+k);
if(m[tmp]==0||m[cur]+1<m[tmp]){
m[tmp]=m[cur]+1;
q.push(tmp);
}
}
}
sort(all(board));
return m[board]==0 ? -1 :m[board]-1;
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
map<vector<int>,int> m;
queue<vector<int> > q;
class SortingGame {
public:
int fewestMoves(vector<int> board, int k) {
int n=board.size();
m.clear();
m[board]=1;
q.push(board);
while(!q.empty()){
vector<int> cur=q.front();
q.pop();
for(int i=0;i+k<=n;i++){
vector<int> tmp=cur;
reverse(tmp.begin()+i,tmp.begin()+i+k);
if(m[tmp]==0||m[cur]+1<m[tmp]){
m[tmp]=m[cur]+1;
q.push(tmp);
}
}
}
sort(all(board));
return m[board]==0 ? -1 :m[board]-1;
}
};