POJ3050 Hopscotch

探索やるだけ。に見えて定数倍重いので普通にやるとTLEする。
setとか使って謎の枝狩りを仕込む。こんな枝狩り見たことないなぁ。
TLEぎりぎりで通る。

#include<stdio.h>
#include "stdafx.h"
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
using namespace std;
int main()
{
	int map[5][5];
	for(int i=0;i<5;i++)
	{
		for(int j=0;j<5;j++)
		{
			scanf("%d",&map[i][j]);
		}
	}
	queue<pair<vector<int>,pair<int,int> > >que;
	for(int k=0;k<5;k++)
	{
		for(int l=0;l<5;l++)
		{
			vector<int>zan;
			zan.push_back(map[k][l]);
			que.push(make_pair(zan,make_pair(k,l)));
		}
	}
	vector<vector<int> >ret;
	set<pair<vector<int>,pair<int,int> > >se;
	int fuga=0;
	for(;;)
	{
		if(que.empty())
		{
			break;
		}
		fuga++;
		pair<vector<int>,pair<int,int> >zan=que.front();
		que.pop();
		if(zan.first.size()==6)
		{
			ret.push_back(zan.first);
			continue;
		}
		pair<int,int>kou[4];
		int piyo=0;
		if(zan.second.first!=0)
		{
			kou[piyo]=(make_pair(zan.second.first-1,zan.second.second));
			piyo++;
		}
		if(zan.second.first!=4)
		{
			kou[piyo]=(make_pair(zan.second.first+1,zan.second.second));
			piyo++;
		}
		if(zan.second.second!=0)
		{
			kou[piyo]=(make_pair(zan.second.first,zan.second.second-1));
			piyo++;
		}
		if(zan.second.second!=4)
		{
			kou[piyo]=(make_pair(zan.second.first,zan.second.second+1));
			piyo++;
		}
		for(int m=0;m<piyo;m++)
		{
			vector<int>hoge=zan.first;
			hoge.push_back(map[kou[m].first][kou[m].second]);
			set<pair<vector<int>,pair<int,int> > >::iterator it=se.find(make_pair(hoge,kou[m]));
			if(it==se.end())
			{
				que.push(make_pair(hoge,kou[m]));
				se.insert(make_pair(hoge,kou[m]));
			}
		}
	}
	sort(ret.begin(),ret.end());
	vector<int>now;
	int sum=0;
	for(int n=0;n<ret.size();n++)
	{
		if(now!=ret[n])
		{
			sum++;
			now=ret[n];
		}
	}
	printf("%d\n",sum);
}