文档章节

Algorithm Game-Unique Paths

Wayen007
 Wayen007
发布于 2017/08/29 13:53
字数 442
阅读 1
收藏 0

Unique Paths:

  •  A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
  •  The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
  •  How many possible unique paths are there?

         

C# codes

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace UniquePaths
{
    class UniquePaths
    {
        static void Main(string[] args)
        {
            Console.Write("Please input m and n values for Array, the row is m, the column is n\n");
            // Read data from console.
            string str = Console.ReadLine();
            string[] nums = str.Split(new string[] { " " }, StringSplitOptions.None);
            int m = Convert.ToInt32(nums[0]);
            int n = Convert.ToInt32(nums[1]);       

            // Initialization an array
            Console.Write("m={0}, n={1}\n", m, n);
            if (m == 0 || n == 0)
            {
                Console.Write("Please input two valid numbers,m:{0} and n:{1} must be more than 0.\n", m, n);
            }
            Int64[,] array = new Int64[m, n];

            // When the row or column is 0, the only one way to arrive every form,so we set 1 for them.
            for (int i = 1; i < m; i++)
            {
                array[i, 0] = 1;
            }
            for (int j = 1; j < n; j++)
            {
                array[0, j] = 1;
            }

            // "-2" stand for "Start"
            array[0, 0] = -2;
            // "-1" stand for "Finish"
            array[m - 1, n - 1] = -1;

            // Before changing data, we can check the array values.
            // If the value is 0, it stand for "Never Arriving". Otherwise, it stand for ways to arrive here.
            Console.Write("Verify and print all of this array data:\n\n");
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Console.Write("  " + array[i, j]);
                }
                Console.Write("\n");
            }

            bool key;
            // If the row or column is 1,there is only one way to reach "Finish";
            if (m == 1 || n == 1)
            {
                array[m - 1, n - 1] = 1;
                key = false;
            }
            else
            {
                key = true;
            }
            while (key)
            {
                for (int i = 0; i < m; i++)
                {
                    for (int j = 0; j < n; j++)
                    {
                        // Judge this process whether it will continue to run or not.
                        if (array[i, j] != -1)
                        {
                            key = true;
                        }
                        else
                        {
                            key = false;

                        }

                        // Skip row=0 or column=0
                        //if(array[i,j]==1|| array[i, j] ==-2)
                        if (i == 0 || j == 0)
                        {
                            continue;
                        }
                        else
                        {
                            array[i, j] = array[i - 1, j] + array[i, j - 1];
                        }
                    }
                }
            }

            Console.Write("After running this programme and get result:\n");
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Console.Write("  " + array[i, j]);
                }
                Console.Write("\n");
            }
            Console.Write("There are {0} ways from 'Start' to 'Finish'.\n\n", array[m - 1, n - 1]);
            Console.ReadKey();
        }
    }
}

Results:

           

© 著作权归作者所有

共有 人打赏支持
Wayen007
粉丝 0
博文 4
码字总数 1466
作品 0
闵行
QA/测试工程师
决战Leetcode: easy part(51-96)

本博客是个人原创的针对leetcode上的problem的解法,所有solution都基本通过了leetcode的官方Judging,个别未通过的例外情况会在相应部分作特别说明。 欢迎互相交流! email: tomqianmaple@...

qq_32690999
02/09
0
0
再译《A *路径搜索入门》之五

■实施上的注意事项 Notes on Implementation 现在您了解了基本的方法,当你编写自己的程序时,有一些额外的事情要考虑。下面给出我用C ++和Blitz Basic编写的程序,用其他语言也同样有效。 ...

放个屁
2015/06/11
0
0
Leetcode 62. Unique Paths

最一开始直接用dfs recursion暴力遍历出所有的route,但是超时不给过TLE了 然后去网上搜索解法发现可以结合缓存,保留一个f[m][n]数组把遍历到的点的path数保存到数组里,下次再走到这一点就...

s360564346
2016/12/15
12
0
Python一课一练(利用session来保存用户输入)

平常我们在浏览器里输入的时候会用到缓存,在python里由web库里的session来实现,代码很简单,我们会用到四个文件:

fantasiter
2016/12/28
12
0
java.lang.UnsatisfiedLinkError: no xxx in java.library.path

新入手的mac pro,安装jdk1.764位的,然后安装eclipse也是64位的,然后导入一个之前的windows下的java工程,因为工程用到自由的类库xxx.so(之前写好的也是64位,而且已经在阿里云服务器上部署...

one_day
2015/10/05
2.1K
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

获取多个集合列表的笛卡尔积

获取多个集合笛卡尔积 电商中典型业务场景:商品搜索 单属性属性值之间为并查询 不同属性的属性值之间查询为与查询 import java.util.ArrayList;import java.util.List;/** * Created w...

键走偏锋
10分钟前
0
0
echarts 迁移地图 控制鼠标缩放大小比例

在网上找了好久没有找到解决方式,还是重新看了一下文档,终于找到的解决方案, zoom:1, //默认显示级别 scaleLimit:{min:1,max:3}, // 缩放级别 echarts 文档-配置项链接 http://echarts.b...

心驰
13分钟前
0
0
Boot2Docker ISO is out-of-date,

Boot2Docker ISO is out-of-date, downloading the latest release. 使用docker-machine时无法更新Boot2Docker ISO导致创建vm machine失败 解决方法:关闭网络,创建好之后再开启...

writeademo
21分钟前
0
0
在 Tomcat 中设置 Tapestry 框架的 html 热加载

如果开发中使用到了 Tapestry 这个框架,如果事先没有设置过的话,开发的时候 html 是不会热加载的,也就是说修改了 html 文件,不能刷新浏览器后立马看到修改完的效果,必须先重新启动应用服...

LeoXu
43分钟前
0
0
【微服务】开启巨石应用到微服务的探索

背景 在过去的一年时间里,我一直在从事一件事情,将现有的单体应用(巨石应用)向微服务改造。 接下来,将持续整理一些在微服务路上的学习与成长。 为什么要做微服务 单体应用,开发、部署简...

艳沐石
53分钟前
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部