给定一个矩阵 [n,n] 我想找出我们可以从 [0,0] 到 [n,n] 非递归地达到多少种方式。
我的方法是
- 创建一个结构节点来存储到目前为止行进的行、列和路径
- 将节点添加到队列
- 遍历队列直到不为空。增加行,增加列。添加到队列
- 如果 row=n, col=n 则打印路径
问题
- 是否有不同的方式来存储行、列和路径
- 如果 n 非常大,将节点存储在 Queue 中可能会出现问题。我们怎样才能避免这种情况?
请不要我不是在寻找递归解决方案。我在许多面试论坛上看到这样的问题,所以想知道这是否是正确的方法。
下面是Node的结构和功能
struct Node
{
public int row;
public int col;
public string path;
public Node(int r, int c, string p)
{
this.row = r;
this.col = c;
this.path = p;
}
}
public static void NextMoveNonRecursive(int max)
{
int rowPos;
int colPos;
string prevPath = "";
Node next;
while (qu.Count > 0)
{
Node current = qu.Dequeue();
rowPos = current.row;
colPos = current.col;
prevPath = current.path;
if (rowPos + 1 == max && colPos + 1 == max)
{
Console.WriteLine("Path = ..." + prevPath);
TotalPathCounter++;
}
if (rowPos + 1 < max)
{
if (prevPath == "")
prevPath = current.path;
prevPath = prevPath + ">" + (rowPos + 1) + "" + (colPos);
next = new Node(rowPos + 1, colPos, prevPath);
qu.Enqueue(next);
prevPath = "";
}
if (colPos + 1 < max)
{
if (prevPath == "")
prevPath = current.path;
prevPath = prevPath + ">" + (rowPos) + "" + (colPos+1);
next = new Node(rowPos, colPos+1, prevPath);
qu.Enqueue(next);
prevPath = "";
}
}
}