メンバー > SGHR > topcoder > NarrowPassage2Easy


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

問題


ジャンル

幅優先探索

解説

大きさの違う狼が何匹か狭い路地にいて、二匹の狼の大きさの和が路地の幅より大きいとその二匹はすれ違うことができないとする。
このとき初期配置から狼の順番を入れ替えていって到達できるパターンは何通りか、という問題。
任意の隣り合う二匹をスワップして得られた配置をキューに入れ、そこから到達できるパターンを幅優先で探索。
かぶりがないようセットを使ってすでに探索したパターンは排除する。

コード

  1. #include<cmath>
  2. #include<cstdlib>
  3. #include<string>
  4. #include<sstream>
  5. #include<vector>
  6. #include<iostream>
  7. #include<queue>
  8. #include<deque>
  9. #include<map>
  10. #include<set>
  11. #include<stack>
  12. #include<list>
  13. #include<algorithm>
  14. using namespace std;
  15.  
  16. class NarrowPassage2Easy{
  17. public:
  18. int count(vector <int> size, int maxSizeSum) {
  19. int ans = 0;
  20. queue< vector<int> > q;
  21. set< vector<int> > s;
  22. vector<int> v;
  23. v.resize(size.size());
  24. for(int i=0; i<size.size(); i++) v[i] = i;
  25. q.push(v);
  26.  
  27. while(!q.empty()){
  28. vector<int> v = q.front();
  29. if(s.count(v) == 0){
  30. s.insert(v);
  31. //for(int i=0; i<v.size(); i++) cout << v[i] << " ";
  32. //cout << endl;
  33. for(int i=0; i<v.size()-1; i++){
  34. vector<int> w = v;
  35. if((size[w[i]]+size[w[i+1]]) <= maxSizeSum){
  36. swap(w[i], w[i+1]);
  37. if(s.count(w) == 0){
  38. q.push(w);
  39. }
  40. }
  41. }
  42. ans++;
  43. }
  44. q.pop();
  45. }
  46. return ans;
  47. }
  48. };