华容道问题求解

（���上文）

布局的hash 值计算

笔者也参考了之前的一些文章，很多文章提到了怎么节省存贮空间来查找最优解，这不是笔者的目的。笔者的目的比较单一，就是找到最优解就行了。因此并没有在存贮上面进行过多的优化，曾经尝试使用移位指令进行棋子的移动，然而并没有发现运行速度比使用庞大的对象速度更快。（或许是算法的问题）因此索性就使用了高级语言的高级方法，放弃了对存贮空间的限制和约束。基于前面的设计，每个布局保存在一个4*5的整数数组里面（保存的棋子的ID），因此为了简单起见笔者将这个20个整数构成一个字符串，然后利用C#提供的现有的字符串hash函数，就得到了这个布局的hash值。这个方法简单粗暴，并不美丽，但是解决问题就行了。

一个细节：在实际棋子的移动过程当中，我们关心的是棋子的形状而非棋子的名字，因此在棋子布局的时候，尽管每个棋子都赋予了名字，在进行查找的时候，是忽略了这些名字的。因此在使用DFS结合Dijkstra 算法查找时会出现名字改变的情况，这里笔者没有对名字进行一致处理，因为这种处理对解法其实没有什么帮助，只是界面看着更连贯些。（具体原因也不解释了，很简单）。在BFS的查找过程当中，不会有这个问题。

hash 函数如下：

      public int GetMyHashCode(GameState gameState)      {          string val = string.Empty;          for (int i = 1; i               for (int j = 1; j                   var pcs  = gameState.layoutOfObj[i, j];                                    val += pcs.GetHrdType().ToString();              }          }          return val.GetHashCode();      }                     var toHashCode = GetMyHashCode(dest);           var frmHashCode = GetMyHashCode(source);           AdjustShortPath(dest, toHashCode, frmHashCode);           AddEdge(frmHashCode, toHashCode, 1);       }       private void PushState(StateS          (int, int) lastItem;          if (hCodeAndShotShortPathDict.TryGetValue(toHashCode, out lastItem))          {              if (lastItem.Item2  dest.bestSteps)              {              //这是笔者增加的视图记录最短路径的判断，DFS时，找到了比原来步骤少的方法，但是不是最优的。BFS时，这里执行不到。                  hCodeAndShotShortPathDict[toHashCode] = (frmHashCode, dest.bestSteps);              }              //hCodeAndShotShortPathDict.Add(toHashCode, (dest.basePcs, selPcs.idx, dstPcs.idx, frmHashCode, pathLen));          }          else          {          // 查找过程记录，BFS时，记录的就是最佳结果              hCodeAndShotShortPathDict.Add(toHashCode, (frmHashCode, dest.bestSteps));          }      }         //allShortPath = allShortPath2;         if (allShortPath == null)         {             MessageBox.Show(string.Format("The shortest path is now being searched ,wait for a moment."), "Notice", MessageBoxButtons.OK, MessageBoxIcon.Exclamation);             return;         }         //solutionPcsIdx 布局数组索引         //cbbSolutionIdx 保存在CBB 中的结果布局索引（hash 值）         if (solutionPcsIdx = 0 && solutionPcsIdx  
函数中增加了 动画部分，因此做了相应的处理，这一部分将在后文赘述。
 
回放时，需要用户点击回放按钮。也支持了Undo功能，以方便用户观察棋子的移动过程。目前，执行Undo功能时没有做动画处理。
 
说明如下：
首先在下拉列表中选择一个布局的Hash值，例如第一个（就应该是最少步骤那个，BFS决定的）
 
点击[>>],棋子移动一步
 
点击[