نمايش پست تنها
قديمي ۱۲-۲۵-۱۳۸۸, ۱۲:۳۲ بعد از ظهر   #6 (لینک دائم)
Astaraki Female
Administrator
 
آواتار Astaraki
 
تاريخ عضويت: خرداد ۱۳۸۷
محل سكونت: تهران-کرج!
پست ها: 3,465
تشكرها: 754
16,337 تشكر در 3,127 پست
My Mood: Mehrabon
ارسال پيغام Yahoo به Astaraki
Cool

حالت خطی
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;
}
Astaraki آفلاين است   پاسخ با نقل قول
از Astaraki تشكر كرده اند:
astronomer (۰۷-۱۷-۱۳۹۲), ayfer.a11 (۰۸-۴-۱۳۹۰), elit (۰۷-۲۳-۱۳۹۱), green_Dream (۱۲-۲۸-۱۳۸۸), khokho (۰۱-۲۱-۱۳۹۰), pincode (۰۸-۴-۱۳۹۲), rouhallah (۱۲-۲۹-۱۳۸۸), Sahebi (۰۱-۱۱-۱۳۸۹), samane_89 (۱۲-۲۸-۱۳۸۹), وجیهه نصر (۰۸-۷-۱۳۹۲), voice (۰۸-۴-۱۳۹۲), zari11368 (۱۲-۱۷-۱۳۹۰)