スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

AOJ 0121 Seven Puzzle

幅優先探索の問題
まず考えたのは、初期状態から0をどんどん移動させて行く方法。
パズルの状態はstringで表現している。
mapで状態とそこまでの最短距離を対応させ、
mapに存在するかどうかでたどり着いたことがあるかを確認。
ただ、これだとTLEをくらう。

//TLEをくらうコード

void swap(char *a,char *b){
char temp = *a;
*a = *b;
*b = temp;
}

int main(){
int dx[] = {+1,-1,+4,-4};
while(1){
string input = "";
char temp;
for(int i=0;i<8;i++){
if(cin >> temp){
input.push_back(temp);
}else{
return 0;
}
}

queue que;
map d;
que.push(input);
d[input] = 0;

while(que.size()){
string q = que.front(); que.pop();
if(q=="01234567"){
break;
}
int x = q.find("0");
for(int i=0;i<4;i++){
int next = x + dx[i];
if( next>=0 && next<=7 && !(x==3&&next==4) && !(x==4&&next==3) ){
string nextq = q;
swap(&nextq[x],&nextq[next]);
if(d.find(nextq)==d.end()){
que.push(nextq);
d[nextq] = d[q] + 1;
}
}
}
}
cout << d["01234567"] << endl;
}
}



inputは1000個まで与えられるので、
毎回一から探索していっているのでは無駄が多い。
そもそも、ありえる状態は8!通りしかないから
そろった状態からたどりつけるすべての状態への最短距離を計算しておき
inputに対応した最短距離を出力するほうがいい。
同じようにmapを使って状態と最短距離を対応させる。


//通ったコード

void swap(char *a,char *b){
char temp = *a;
*a = *b;
*b = temp;
}

int main(){
int dx[] = {+1,-1,+4,-4};

string start = "01234567";

queue que;
map d;
que.push(start);
d[start] = 0;

while(que.size()){
string q = que.front(); que.pop();
int x = q.find("0");
for(int i=0;i<4;i++){
int next = x + dx[i];
if( next>=0 && next<=7 && !(x==3&&next==4) && !(x==4&&next==3) ){
string nextq = q;
swap(&nextq[x],&nextq[next]);
if(d.find(nextq)==d.end()){
que.push(nextq);
d[nextq] = d[q] + 1;
}
}
}
}

while(1){
string input = "";
char temp;
for(int i=0;i<8;i++){
if(cin >> temp){
input.push_back(temp);
}else{
return 0;
}
}
cout << d[input] << endl;
}

}


コメントの投稿

非公開コメント

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。