ProgramCaiCai · February 15, 2014 15:02 · Feb 15, 2014
diff --git a/aiplan_pa1_astat.cpp b/aiplan_pa1_astat.cpp
@@ -0,0 +1,129 @@
+#include <iostream>
+#include <stdio.h>
+#include <string.h>
+#include <algorithm>
+#include <queue>
+#include <cmath>
+#include <map>
+using namespace std;
+
+const int dx[]={0,0,1,-1};
+const int dy[]={1,-1,0,0};
+
+struct Stat{
+    int a[9];
+
+    int zeropos() const{
+        for(int i=0;i<9;i++) if(a[i]==0) return i;
+    }
+    int h() const {
+        int ret = 0;
+        for(int i=0;i<9;i++) {
+            int x = i/3;
+            int y = i%3;
+            int ox = a[i]/3;
+            int oy = a[i]%3;
+            ret +=  abs(x-ox) + abs(y-oy);
+        }
+        return ret;
+    }
+
+    bool canmakemove(int dir) const{
+        int zp = zeropos();
+        int x = zp/3;
+        int y = zp%3;
+        x+=dx[dir];
+        y+=dy[dir];
+        return x>=0 && x<3 && y>=0 && y<3;
+    }
+    Stat makemove(int dir) const{
+        int zp = zeropos();
+        int x = zp/3;
+        int y = zp%3;
+        x+=dx[dir];
+        y+=dy[dir];
+        Stat ret;
+        for(int i=0;i<9;i++) ret.a[i]=a[i];
+        swap(ret.a[zp],ret.a[x*3+y]);
+        return ret;
+    }
+    bool operator<(const Stat &b) const {
+        for(int i=0;i<9;i++) if(a[i]!=b.a[i]) return a[i]<b.a[i];
+        return false;
+    }
+    void print() {
+        printf("[");
+        for(int i=0;i<9;i++) printf(" %d",a[i]);
+        printf("]\n");
+    }
+};
+
+typedef pair<int,Stat>  PIS;
+
+
+priority_queue<PIS,vector<PIS>,greater<PIS> > pq;
+map<Stat,int> mp;
+
+
+int astar(Stat start){
+    while(!pq.empty()) pq.pop();
+    mp.clear();
+    pq.push(PIS(start.h(),start));
+    mp[start]=0;
+    while(!pq.empty()){
+        PIS pis = pq.top();
+        pq.pop();
+        Stat s = pis.second;
+        if(s.h()==0) {
+            return mp[s];
+        }
+
+        //s.print();
+        //printf("%d\n",mp[s]);
+        for(int i=0;i<4;i++) if(s.canmakemove(i)){
+            Stat ns = s.makemove(i);
+            if((mp.find(ns)== mp.end()) || mp[s]+1<mp[ns]) {
+                mp[ns]=mp[s]+1;
+                pq.push(PIS(ns.h()+mp[ns],ns));
+            }
+        }
+    }
+    return 10000;
+}
+
+queue<Stat> q;
+int countbfs(Stat s,int dep=27){
+    while(!q.empty()) q.pop();
+    q.push(s);
+    mp.clear();
+    mp[s]=0;
+    int cnt=0;
+    while(!q.empty()){
+        Stat s= q.front();
+        q.pop();
+        for(int i=0;i<4;i++) if(s.canmakemove(i)){
+            Stat ns = s.makemove(i);
+            if((mp.find(ns)== mp.end())){
+                mp[ns]=mp[s]+1;
+                if(mp[ns]==dep) cnt++;
+                if(mp[ns]>dep) return cnt;
+                q.push(ns);
+            }
+        }
+    }
+    return cnt;
+}
+
+Stat start;
+
+
+
+int main()
+{
+    cout<<"Input start state:  eg. [1 6 4 8 7 0 3 2 5] (without parentheses)"<<endl;
+    for(int i=0;i<9;i++) cin>>start.a[i];
+
+    //cout<<astar(start)<<endl;
+    cout<<countbfs(start)<<endl;
+    return 0;
+}