文档章节

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
2018/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
唯一路径问题II

原题   Follow up for “Unique Paths”:   Now consider if some obstacles are added to the grids. How many unique paths would there be?   An obstacle and empty space is mark......

一贱书生
2016/12/16
1
0

没有更多内容

加载失败,请刷新页面

加载更多

jenkins 配置

1. ssh-keygen -t rsa 2. 配置 GitLab 用户 创建一个用户或选择一个已有用户,用来让 Jenkins 和 GitLab API 交互。这个用户将需要是全局的管理员或添加进每个组/工程,并作为成员。需要开发...

关上越
14分钟前
1
0
中台迷思

到处都在喊中台,到处都是中台,中台这个词在我看来已经被滥用了。 在有些人眼里:中台就是技术平台,像微服务开发框架、Devops平台、PaaS平台,容器云之类的,人们都叫它“技术中台”。 在有...

老道士
21分钟前
1
0
Linux命令参数解析

Linux命令参数 通过一个例子来理解什么是Linux命令参数。以Linux中常用的删除命令“rm”为例,输入“rm --help”可以看到如下信息,其中红色框内的就是命令参数。经常使用Linux对命令参数应该...

RongJinhui0
24分钟前
1
0
边缘节点服务ENS重磅升级 阿里云首次定义“边缘云计算”概念层层深入

摘要: 在这一横一纵之间,阿里云在2018年率先提供了基于运营商边缘节点和网络的弹性分布式算力资源平台,也就是边缘节点服务ENS,连接最后10公里的ENS可以帮助用户将计算、转发等业务下沉至...

阿里云云栖社区
29分钟前
1
0
阿里云 Aliplayer高级功能介绍(四):直播时移

基本介绍 时移直播基于常规的HLS视频直播,直播推流被切分成TS分片,通过HLS协议向播放用户分发,用户请求的m3u8播放文件中包含不断刷新的TS分片地址;对于常规的HLS直播而言,TS分片地址及相...

阿里云官方博客
32分钟前
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部