SRM 651 Div1 Medium FoxConnection3

2次元グリッド上にきつねがN匹いる (N <= 6)
すべてのきつねが辺で連結になるように動かすとき、最小で何ステップでできるか？(きつねは重なることは出来ない)

まず、1次元の場合には、中央値に寄せるのが一番効率がよい。 (N が偶数のときは、真ん中の2つの値の平均を中央値とする。)
2次元の場合にもできるだけ中央に寄せるのがよい。
中央に近づけたあとは、高々 5*5 マスのグリッド上にすべてのきつねがいることになるので、BFS で調べれば良い。(状態数は、高々25C6 (=177,100)で、遷移も高々24なので、map を使っても十分間に合う。)

vector<int> x, y, x2, y2;
int n;
map<vector<int>, int> dp;
int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
int h, w;

struct UF {
	vector<int> par, rank, sz;
	
	void init(int n){
		par = rank = vector<int>(n, 0);
		sz = vector<int>(n, 1);
		for(int i = 0; i < n; i++){
			par[i] = i;
		}
	}
	
	int find(int x){
		if(par[x] == x){
			return x;
		}else{
			return par[x] = find(par[x]);
		}
	}

	int size(int x){
		return sz[find(x)];
	}
	
	void unite(int x, int y){
		x = find(x);
		y = find(y);
		if(x == y) return;
		
		if(rank[x] < rank[y]){
			par[x] = y;
			sz[y] += sz[x];
		}else{
			par[y] = par[x];
			if(rank[x] == rank[y]) rank[y]++;
			sz[x] += sz[y];
		}
	}
	
	bool same(int x, int y){
		return find(x) == find(y);
	}
};


class FoxConnection3 {
	public:
	bool check(vector<int> &v){
		UF uf;
		uf.init(n);
		rep(i, n) rep(j, n){
			int a = v[i]/w, b = v[i]%w, c = v[j]/w, d = v[j]%w;
			if(abs(a-c)+abs(b-d)==1) uf.unite(i, j);
		}
		return uf.size(0)==n;
	}
	void comp(vector<int> &x, ll &res){
		for(int i = 4; i >= 0; i--){
			int cnt = 0, cnt2 = 0;
			rep(j, n){
				if(x[j]==i) cnt++;
				else if(x[j]>i) cnt2++;
			}
			if(cnt==0){
				rep(j, n) if(x[j]>i) x[j]--;
				res += min(cnt2, n-cnt2);
			}
		}
	}
	long long minimalSteps(vector <int> x_, vector <int> y_) {
		x=x_;y=y_;
		n = x.size();
		x2=x; y2=y;
		sort(all(x2)); sort(all(y2));
		ll xx = ((ll)x2[n/2]+x2[(n-1)/2])/2, yy = ((ll)y2[n/2]+y2[(n-1)/2])/2;
		cerr<<xx<<endl;
		ll res = 0;
		rep(i, n){
			if(x[i]<xx-2){
				res += xx-2-x[i];
				x[i] = xx-2;
				rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) x[i]++,res++;
			}
			if(y[i]<yy-2){
				res += yy-2-y[i];
				y[i] = yy-2;
				rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) y[i]++,res++;
			}
			if(x[i]>xx+3){
				res += x[i]-xx-3;
				x[i] = xx+3;
				rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) x[i]--,res++;
			}
			if(y[i]>yy+3){
				res += y[i]-yy-3;
				y[i] = yy+3;
				rep(_, 2) rep(j, n) if(i!=j&&x[i]==x[j]&&y[i]==y[j]) y[i]--,res++;
			}
		}
		rep(i, n) x[n-i-1] -= xx-2;
		rep(i, n) y[n-i-1] -= yy-2;
		comp(x, res);
		comp(y, res);
		h = w = 1;
		rep(i, n) chmax(h, x[i]+1);
		rep(i, n) chmax(w, y[i]+1);
		vector<int> v(n);
		rep(i, n) v[i] = x[i]*w+y[i];
		sort(all(v));
		dp[v] = 0;
		queue<vector<int>> q;
		q.push(v);
		while(true){
			vector<int> vv = q.front(); q.pop();
			int t = dp[vv];
			if(check(vv)) return res+t;
			for(auto &a: vv){
				int aa = a;
				rep(i, 4){
					int ax = aa/w+dx[i], ay = aa%w+dy[i];
					if(ax<0||ax>=h||ay<0||ay>=w) continue;
					a = ax*w+ay;
					vector<int> vv2(vv);
					int cnt = 0;
					rep(j, n) if(vv2[j]==a) cnt++;
					if(cnt>1) continue;
					sort(all(vv2));
					if(!dp.count(vv2)){
						dp[vv2] = t+1;
						q.push(vv2);
					}
				}
				a = aa;
			}
		}
	}
};