メンバー/SGHR/topcoder/NarrowPassage2Easy - 阪大理学部科学計算・開発サークル -Circle for Science Caluculation and Development-

問題

ジャンル

幅優先探索

解説

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

コード

#include<cmath>
#include<cstdlib>
#include<string>
#include<sstream>
#include<vector>
#include<iostream>
#include<queue>
#include<deque>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<algorithm>
using namespace std;
 
class NarrowPassage2Easy{
public:
  int count(vector <int> size, int maxSizeSum) {
    int ans = 0;
    queue< vector<int> > q;
    set< vector<int> > s;
    vector<int> v;
    v.resize(size.size());
    for(int i=0; i<size.size(); i++) v[i] = i;
    q.push(v);
 
    while(!q.empty()){
      vector<int> v = q.front();
      if(s.count(v) == 0){
	s.insert(v);
	//for(int i=0; i<v.size(); i++) cout << v[i] << " ";
	//cout << endl;
	for(int i=0; i<v.size()-1; i++){
	  vector<int> w = v;
	  if((size[w[i]]+size[w[i+1]]) <= maxSizeSum){
	    swap(w[i], w[i+1]);
	    if(s.count(w) == 0){
	      q.push(w);
	    }
	  }
	}
	ans++;
      }
      q.pop();
    }
    return ans;
  }
};