文档章节

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

没有更多内容

加载失败,请刷新页面

加载更多

创建第一个react项目

sudo npm i -g create-react-app@1.5.2 create-react-app react-app cd react-apprm -rf package-lock.jsonrm -rf node_modules #主要是为了避免报错npm installnpm start......

lilugirl
今天
3
0
在浏览器中进行深度学习:TensorFlow.js (八)生成对抗网络 (GAN)

Generative Adversarial Network 是深度学习中非常有趣的一种方法。GAN最早源自Ian Goodfellow的这篇论文。LeCun对GAN给出了极高的评价: “There are many interesting recent development...

naughty
今天
0
0
搬瓦工镜像站bwh1.net被DNS污染,国内打不开搬瓦工官网

今天下午(2018年10月17日),继搬瓦工主域名bandwagonhost.com被污染后,这个国内的镜像地址bwh1.net也被墙了。那么目前应该怎么访问搬瓦工官网呢? 消息来源:搬瓦工优惠网->搬瓦工镜像站b...

flyzy2005
今天
7
0
SpringBoot自动配置

本篇介绍下,如何通过springboot的自动配置,将公司项目内的依赖jar,不需要扫描路径,依赖jar的情况下,就能将jar内配置了@configuration注解的类,创建到IOC里面 介绍下开发环境 JDK版本1.8 spr...

贺小五
今天
5
0
命令行新建Maven多项目

参考地址 # DgroupId 可以理解为包名# DartifactId 可以理解为项目名mvn archetype:generate -DgroupId=cn.modfun -DartifactId=scaffold -DarchetypeArtifactId=maven-archetype-quickst......

阿白
今天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部