Algorithm Game-Unique Paths
Algorithm Game-Unique Paths
Wayen007 发表于9个月前
Algorithm Game-Unique Paths
• 发表于 9个月前
• 阅读 1
• 收藏 0
• 评论 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;

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]);
}
}
}

Results:

×