۱۲-۲۵-۱۳۸۸, ۱۲:۳۲ بعد از ظهر
|
#6 (لینک دائم)
|
Administrator
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood:
|
حالت خطی
8puzzle
كد:
#include <iostream>
#include <fstream>
#include <string>
#include <ctime>
#include <map>
#include <queue>
using namespace std;
map <string , int> m;
queue < string > qs;
queue < int > qc,qd;
//struct state{
// string s;
// int c,d;
//};
//queue <state> q;
void puzzle(int cur,string s){
if (m.find(s)==m.end()){
m[s]=qd.front();
if (cur-1>=0 && cur-1<=8 && cur!=6 && cur!=3){
string temp=s;
{char t=temp[cur]; temp[cur]=temp[cur-1]; temp[cur-1]=t; }
qc.push(cur-1);
qd.push(m[s]+1);
qs.push(temp);
}
if (cur+1>=0 && cur+1<=8 && cur!=2 && cur!=5){
string temp=s;
{char t=temp[cur]; temp[cur]=temp[cur+1]; temp[cur+1]=t; }
qc.push(cur+1);
qd.push(m[s]+1);
qs.push(temp);
}
if (cur-3>=0 && cur-3<=8){
string temp=s;
{char t=temp[cur]; temp[cur]=temp[cur-3]; temp[cur-3]=t; }
qc.push(cur-3);
qs.push(temp);
qd.push(m[s]+1);
}
if (cur+3>=0 && cur+3<=8){
string temp=s;
{char t=temp[cur]; temp[cur]=temp[cur+3]; temp[cur+3]=t; }
qc.push(cur+3);
qs.push(temp);
qd.push(m[s]+1);
}
}
qs.pop();
qc.pop();
qd.pop();
}
int main () {
clock_t cl=clock();
ifstream in ("8puzzle.in");
qs.push("123456780");
qc.push(8);
qd.push(0);
while (!qs.empty())
puzzle(qc.front(),qs.front());
int t;
for (in >> t;t>0;--t){
string s,temp;
for (int i=0;i<3;++i)
for (int j=0;j<3;++j){
in >> temp;
if (temp=="-1")
temp="0";
s+=temp;
}
if (m.find(s)==m.end())
cout << "Impossible" << endl;
else
cout << m[s] << endl;
}
cout << "time: " << (clock()-cl) * 0.001 << endl;
return 0;
}
|
|
|