在线时间:8:00-16:00
迪恩网络APP
随时随地掌握行业动态
扫描二维码
关注迪恩网络微信公众号
原题: 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 }
|
2023-10-27
2022-08-15
2022-08-17
2022-09-23
2022-08-13
请发表评论