• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

NO 15 [C#] 峰回路转的格子

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

 

原题:

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     } 

 

 


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
C语言(函数)学习之strstr strcasestr发布时间:2022-07-14
下一篇:
c# GDI+简单绘图(四)发布时间:2022-07-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap