学步园

 

原题：

Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.

How many routes are there through a 2020 grid?

翻译：

/*

 * 解释：

 *  2乘2的正方形，左上角到右下角是这样6种走法。

 * 

 *  那么20*20的正方形呢？

 */

解题思路：

 

 1 /// <summary>   
 2 /// 解题思路：   
 3 /// 1， 我把它想象成了一个网格图。一个只有出度，没有或者不计算入度的图。   
 4 ///         这样的话，用邻接矩阵描述这个图。二维表构造，每行意义如下：   
 5 ///        
 6 ///         [当前节点] -〉[向右的节点]-〉[向下的节点]   
 7 ///        
 8 ///         然后初始化这个邻接矩阵表即可。   
 9 ///       
10 /// 2， 当然也可以用数学公式来求这个答案。   
11 ///        
12 ///         公式是： (长+宽)！/长！* 宽！   
13 ///    
14 /// 3， 请看以下这个结构   
15 ///    
16 ///       0 1 1   
17 ///       1 2 3   
18 ///       1 3 6   
19 ///    
20 ///     6就是答案，在扩大一下这个正方形   
21 ///    
22 ///       0  1  1  1  1   
23 ///       1  2  3  4  5   
24 ///       1  3  6 10 15   
25 ///       1  4 10 20 35   
26 ///       1  5 15 35 70   
27 ///    
28 ///     说白了，这个就是一个杨辉三角。每一个元素的数字表示的意思就是从0到这个点的可能性。   
29 /// </summary>  

 

代码：

 

  1 class GridRoutes   
  2     {   
  3         private int SideLength; // 单边长度   
  4         private int ArrayLength; // 存储每个点的矩阵长度   
  5         private int[][] Arr; // 存储矩阵   
  6         private ulong Count; // 路径总数   
  7         public ulong Result   
  8         {   
  9             get { return this.Count; }   
 10         }   
 11         public GridRoutes(int length)   
 12         {   
 13             this.Count = 0;   
 14             this.SideLength = length;   
 15             this.ArrayLength = this.SideLength * this.SideLength;   
 16             this.Arr = new int[this.ArrayLength][];  
 17             #region 初始化   
 18             for (int i = 0; i < this.Arr.GetLength(0); i++)   
 19             {   
 20                 this.Arr[i] = new int[3];   
 21             }  
 22             #endregion  
 23             #region 4个顶点   
 24             // 起点   
 25             this.Arr[0][0] = 0;   
 26             this.Arr[0][1] = 1;   
 27             this.Arr[0][2] = this.SideLength;   
 28             // 终点   
 29             this.Arr[this.ArrayLength - 1][0] = this.ArrayLength - 1;   
 30             this.Arr[this.ArrayLength - 1][1] = -1;   
 31             this.Arr[this.ArrayLength - 1][2] = -1;   
 32             // 右上   
 33             this.Arr[this.SideLength - 1][0] = this.SideLength - 1;   
 34             this.Arr[this.SideLength - 1][1] = -1;   
 35             this.Arr[this.SideLength - 1][2] = (this.SideLength - 1) + (this.SideLength - 1) + 1;   
 36             //左下   
 37             this.Arr[this.SideLength * (this.SideLength - 1)][0] = this.SideLength * (this.SideLength - 1);   
 38             this.Arr[this.SideLength * (this.SideLength - 1)][1] = this.SideLength * (this.SideLength - 1) + 1;   
 39             this.Arr[this.SideLength * (this.SideLength - 1)][2] = -1;  
 40             #endregion  
 41             #region 去顶点的各条边   
 42             // up   
 43             for (int i = 1; i < this.SideLength - 1; i++)   
 44             {   
 45                 this.Arr[i][0] = i;   
 46                 this.Arr[i][1] = i + 1;   
 47                 this.Arr[i][2] = i + this.SideLength;   
 48             }   
 49             // down   
 50             for (int i = this.SideLength * (this.SideLength - 1) + 1; i < this.ArrayLength - 1; i++)   
 51             {   
 52                 this.Arr[i][0] = i;   
 53                 this.Arr[i][1] = i + 1;   
 54                 this.Arr[i][2] = -1;   
 55             }   
 56             // left   
 57             for (int i = this.SideLength; i < this.SideLength * (this.SideLength - 1); i = i + this.SideLength)   
 58             {   
 59                 this.Arr[i][0] = i;   
 60                 this.Arr[i][1] = i + 1;   
 61                 this.Arr[i][2] = i + this.SideLength;   
 62             }   
 63             // right   
 64             for (int i = this.SideLength * 2 - 1; i < this.ArrayLength - 1; i = i + this.SideLength)   
 65             {   
 66                 this.Arr[i][0] = i;   
 67                 this.Arr[i][1] = -1;   
 68                 this.Arr[i][2] = i + this.SideLength;   
 69             }  
 70             #endregion  
 71             #region 中间所有点   
 72             for (int i = 2; i < this.SideLength; i++) // 行数   
 73             {   
 74                 for (int j = 2; j < this.SideLength; j++) // 列数   
 75                 {   
 76                     int tmp = (j - 1) + this.SideLength * (i - 1);   
 77                     this.Arr[tmp][0] = tmp;   
 78                     this.Arr[tmp][1] = tmp + 1;   
 79                     this.Arr[tmp][2] = tmp + this.SideLength;   
 80                 }   
 81             }  
 82             #endregion  
 83             #region 显示数组矩阵内容   
 84             for (int i = 0; i < Arr.GetLength(0); i++)   
 85             {   
 86                 Console.WriteLine(string.Format("矩阵序号 {0:}, 往左 {1, 2}, 往右 {2, 2}", Arr[i][0], Arr[i][1], Arr[i][2]));   
 87             }  
 88             #endregion   
 89         }   
 90         /// <summary>   
 91         /// 寻路   
 92         /// </summary>   
 93         /// <param name="index">当前点</param>   
 94         /// <param name="end">目标点</param>   
 95         public void Go(int index, int end)   
 96         {   
 97             if (this.Arr[index][0] == end)   
 98             {   
 99                 //TODO   
100                 this.Count = this.Count + 1;   
101             }   
102             else  
103             {   
104                 if (this.Arr[index][1] != -1)   
105                 {   
106                     Go(this.Arr[index][1], end);   
107                 }   
108                 if (this.Arr[index][2] != -1)   
109                 {   
110                     Go( this.Arr[index][2], end);   
111                 }   
112             }   
113         }   
114     }