会津大学オンラインジャッジ問121

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0121

セブンパズルを題材にした問題。



平凡な問題なので平凡なコードで平凡な順位。

平凡な問題と考え
平凡なコードで理解をし
平凡なコードの手順を考え
平凡なコードを実装し
平凡なコードを提出し
平凡な結果を期待し
平凡な順位に落ち着く。
私こそミスター平凡。


完全ハッシュ関数を実装すればもう少し早くはなるとおもいます。



#include<stdio.h>
#include<map>
#include<queue>
#include<algorithm>

struct S{
int zeroP,count;
int board[8];
bool operator<(const S& s)const{
for(int i=0;i<8;i++){
if(board[i]!=s.board[i])return board[i]<s.board[i];
}
return false;
}
};

int main(){
int moves[8][3]={{0,1,4},
{0,2,5},
{1,6,3},
{2,7,3},
{0,5,4},
{1,4,6},
{2,5,7},
{3,6,7}};
S s,s2;
s.zeroP=0;
s.count=0;
for(int i=0;i<8;i++){
s.board[i]=i;
}
std::map<S,int> memo;
std::queue<S> qu;
qu.push(s);
while(qu.empty()==false){
s=qu.front();
qu.pop();
if(memo.find(s)!=memo.end())continue;
memo[s]=s.count;
s.count++;

for(int i=0;i<3;i++){
s2=s;
s2.zeroP=moves[s.zeroP][i];
if(s.zeroP==s2.zeroP)continue;
std::swap(s2.board[s.zeroP],s2.board[s2.zeroP]);
if(memo.find(s2)!=memo.end())continue;
qu.push(s2);
}
}
while(1){
if(scanf("%d",&s.board[0])==EOF)break;
for(int i=1;i<8;i++){
scanf("%d",&s.board[i]);
}
printf("%d\n",memo[s]);
}
}