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); }