From c9c9af6a310961f2e18bd0b2298a73d2a623e60e Mon Sep 17 00:00:00 2001
From: =?utf8?q?=E9=9B=B7=E8=92=BB?=
 <34390285+hsfzLZH1@users.noreply.github.com>
Date: Mon, 22 Oct 2018 21:27:48 +0800
Subject: [PATCH] Update astar.md
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

修正了“八数码问题”的代码算法错误的问题
---
 docs/search/astar.md | 91 +++++++++++++++++++++++++++++-----------------------
 1 file changed, 51 insertions(+), 40 deletions(-)

diff --git a/docs/search/astar.md b/docs/search/astar.md
index 3ba50c43..0a614aa6 100644
--- a/docs/search/astar.md
+++ b/docs/search/astar.md
@@ -33,50 +33,61 @@ $h$ 函数可以定义为，不在应该在的位置的数字个数。
 代码实现：
 
 ```cpp
-#include <algorithm>
-#include <cstdio>
+#include<cstdio>
+#include<cstring>
+#include<algorithm>
+#include<queue>
+#include<set>
 using namespace std;
-int fx[9] = {0, 1, 1, 1, 2, 3, 3, 3, 2}, fy[9] = {0, 1, 2, 3, 3, 3, 2, 1, 1};
-int xx[4] = {1, -1, 0, 0}, yy[4] = {0, 0, -1, 1}, a[4][4] = {}, n, m, x, y, z,
-    X, Y, ans;
-int h() {
-  int ans = 0;
-  for (int i = 1; i <= 3; i++)
-    for (int j = 1; j <= 3; j++)
-      if (a[i][j]) ans += abs(i - fx[a[i][j]]) + abs(j - fy[a[i][j]]);
-  return ans;
+const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
+int fx,fy;
+char ch;
+struct matrix
+{
+    int a[5][5];
+    bool operator<(matrix x)const{for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)if(a[i][j]!=x.a[i][j])return a[i][j]<x.a[i][j];return false;}
+}f,st;
+int h(matrix a)
+{
+    int ret=0;
+    for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)if(a.a[i][j]!=st.a[i][j])ret++;
+    return ret;
 }
-void dfs(int tf, int X, int Y, int g) {
-  int H = h();
-  if (!H) {
-    ans = g;
-    return;
-  }
-  if (g == tf || ans || H + g > tf) return;
-  for (int i = 0; i < 4; i++) {
-    int x = X + xx[i], y = Y + yy[i];
-    if (x && y && x <= 3 && y <= 3) {
-      swap(a[X][Y], a[x][y]);
-      dfs(tf, x, y, g + 1);
-      swap(a[X][Y], a[x][y]);
+struct node
+{
+    matrix a;int t;
+    bool operator<(node x)const{return t+h(a)>x.t+h(x.a);}
+}x;
+priority_queue<node>q;
+set<matrix>s;
+int main()
+{
+    st.a[1][1]=1;st.a[1][2]=2;st.a[1][3]=3;
+    st.a[2][1]=8;st.a[2][2]=0;st.a[2][3]=4;
+    st.a[3][1]=7;st.a[3][2]=6;st.a[3][3]=5;
+    for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)
+    {
+        scanf(" %c",&ch);
+        f.a[i][j]=ch-'0';
     }
-  }
-}
-int main() {
-  for (int i = 1; i <= 3; i++)
-    for (int j = 1; j <= 3; j++) {
-      char c;
-      scanf(" %c", &c);
-      a[i][j] = c - '0';
-      if (!a[i][j]) X = i, Y = j;
+    q.push({f,0});
+    while(!q.empty())
+    {
+        x=q.top();q.pop();
+        if(!h(x.a)){printf("%d\n",x.t);return 0;}
+        for(int i=1;i<=3;i++)for(int j=1;j<=3;j++)if(!x.a.a[i][j])fx=i,fy=j;
+        for(int i=0;i<4;i++)
+        {
+            int xx=fx+dx[i],yy=fy+dy[i];
+            if(1<=xx&&xx<=3&&1<=yy&&yy<=3)
+            {
+                swap(x.a.a[fx][fy],x.a.a[xx][yy]);
+                if(!s.count(x.a))s.insert(x.a),q.push({x.a,x.t+1});
+                swap(x.a.a[fx][fy],x.a.a[xx][yy]);
+            }
+        }
     }
-  for (int i = 0;; i++) {
-    dfs(i, X, Y, 0);
-    if (ans) {
-      printf("%d\n", ans);
-      return 0;
-    };
-  }
+    return 0;
 }
 ```
 
-- 
2.11.0