百度之星试题每周一练

百度之星，是全球最大的中文搜索引擎，百度公司面向中国高校学生和编程爱好者所举办的高水平的程序设计大赛。他所考试的题目，全部都是算法的题目。

鄙人虽然是一个.net程序员，在工作之余，喜爱算法。 这个问题非常的巧，故而分享给大家，我想到一种超简单方法，提供大家，希望对大家起了一个开阔思路的作用。

首先，题意是这样的：

八方块移动游戏要求从一个含 8 个数字 （用 1-8 表示） 的方块以及一个空格方块 （用 0 表示） 的 3x3 矩阵的起始状态开始，不断移动该空格方块以使其和相邻的方块互换，直至达到所定义的目标状态。空格方块在中间位置时有上、下、左、右 4 个方向可移动，在四个角落上有 2 个方向可移动，在其他位置上有3 个方向可移动。例如，假设一个 3x3 矩阵的初始状态为： 

8 0 3
2 1 4
7 6 5

目标状态为： 

1 2 3
8 0 4
7 6 5

则一个合法的移动路径为：

8 0 3 8 1 3 8 1 3 2 1 3 1 2 3

2 1 4 => 2 0 4 => 8 0 4 => 8 0 4 

7 6 5 7 6 5 7 6 5 7 6 5 7 6 5 7 6 5

另外，在所有可能的从初始状态到目标状态的移动路径中，步数最少的路径被称为最短路径；在上面的例子中，最短路径为 3 。如果不存在从初试状态到目标状态的任何路径，则称该组状态无解。 请设计有效的（细节请见评分规则）算法找到从八方块的某初试状态到某目标状态的所有可能路径中的最短路径，并用源代码实现。
输入数据：
程序需读入已被命名为 start.txt 的初始状态和已被命名为 goal.txt 的目标状态，这两个文件都由 9 个数字组成（ 0 表示空格， 1-8 表示 8 个数字方块），每行 3 个数字，数字之间用空格隔开。
输出数据：
如果输入数据有解，输出一个表示最短路径的非负的整数；如果输入数据无解，输出 -1 。
自测用例：
如果输入为： start.txt 和 goal.txt ，则产生的输出应为：

又例，如果用
7 8 4
3 5 6
1 0 2
替换 start.txt 中的内容，则产生的输出应为：
17

对于这道题，我思考的思路是这样子的

把每个0-8 的数字，等价于相应横坐标与横坐标的格式例如用一个词典的格式为{7,"0-0"},{8,"0-1"},{4,“0-2”}把两个词典键相等的值,在比较于i，j的值。

相应伪代码如下：

基于这样的思路我们写出的源代码如下所示了：

1 int[,] a1 = new int[3,3]
 2                             {
 3                                 {7 ,8, 4 },
 4                                 {3, 5, 6 },
 5                                 {1, 0, 2} 
 6                             };
 7             int[,] bInts = new int[3,3]
 8                                {
 9                                    {1 ,2 ,3},  
10                                    {8 ,0 ,4}, 
11                                    {7, 6, 5}
12                                };
13             int count = 0;
14          
15             count = 0;
16             Dictionary<int, string> aList = new Dictionary<int, string>();
17             Dictionary<int, string> bList = new Dictionary<int, string>();
18             for (int i = 0; i < 3; i++)
19             {
20                 for (int j = 0; j < 3; j++)
21                 {
22                     aList.Add(a1[i,j], i.ToString() + "-" + j.ToString());
23                     bList.Add(bInts[i,j], i.ToString() + "-" + j.ToString());
24                     Console.WriteLine();
25 
26                     count++;
27 
28                 }
29                 Console.WriteLine();
30             }
31             int sum = 0;
32             for (int i = 0; i < 8; i++)
33             {
34                 string aS = aList[i];
35                 string bS = bList[i];
36 
37                 sum = sum + Math.Abs(Convert.ToInt32(aS.Split('-')[0]) - Convert.ToInt32(bS.Split('-')[0]));
38                 sum = sum + Math.Abs(Convert.ToInt32(aS.Split('-')[1]) - Convert.ToInt32(bS.Split('-')[1]));
39             }
40             Console.WriteLine(sum+ 1);
41             Console.ReadKey();