如何根据一些移动规则枚举从棋盘左下角(a1)到右上角(h8)的唯一路径？

Question

几周前，有人让我找出从棋盘的左下角 (0, 0) 到右上角 (x, y) 的所有不同且独特的路径，前提是 x 和 y 都大于 3，并且只能向上或向右移动。

我到现在还没找到能解释如何在棋盘上导航的算法，所以我想问问你们有没有什么推荐的方法？

换句话说：

你会如何列出从棋盘的左下角 (0, 0) 到右上角 (x, y) 的所有独特路径？你只能向上或向右移动吗？

#

更新于2010年10月16日：

好吧，我对深度优先搜索（DFS）做了一些研究，但不知道从哪里开始，然后我查找了树的先序遍历，得出了这个结论，因为棋盘基本上可以看作是一棵树：

#!/usr/bin/python

class Node(object):

  value = None
  left = None
  right = None

  def SetValue(self, value):
    self.value = value

  def SetLeftNode(self, node):
    self.left = node

  def SetRightNode(self, node):
    self.right = node

def main():
  a = Node()
  a.SetValue((0,0))

  b = Node()
  b.SetValue((1,0))

  c = Node()
  c.SetValue((2,0))

  d = Node()
  d.SetValue((0,1))

  e = Node()
  e.SetValue((1,1))

  f = Node()
  f.SetValue((2,1))

  g = Node()
  g.SetValue((0,2))

  h = Node()
  h.SetValue((1,2))

  i = Node()
  i.SetValue((2,2))

  a.SetLeftNode(b)
  a.SetRightNode(d)

  b.SetLeftNode(g)
  b.SetRightNode(e)

  c.SetLeftNode(f)
  c.SetRightNode(None)

  d.SetLeftNode(e)
  d.SetRightNode(c)

  e.SetLeftNode(h)
  e.SetRightNode(f)

  f.SetLeftNode(i)
  f.SetRightNode(None)

  g.SetLeftNode(None)
  g.SetRightNode(h)

  h.SetLeftNode(None)
  h.SetRightNode(i)

  i.SetLeftNode(None)
  i.SetRightNode(None)

  PreOrderTraversal(a)

def PreOrderTraversal(node):
  if not node:
    return None
  print node.value
  if node.value == (2,2):
    print 'Reached i' 
  PreOrderTraversal(node.left)
  PreOrderTraversal(node.right)

main() 

这个输出结果是：

(0, 0)
(1, 0)
(0, 2)
(1, 2)
(2, 2)
Reached i
(1, 1)
(1, 2)
(2, 2)
Reached i
(2, 1)
(2, 2)
Reached i
(0, 1)
(1, 1)
(1, 2)
(2, 2)
Reached i
(2, 1)
(2, 2)
Reached i
(2, 0)
(2, 1)
(2, 2)
Reached i

它确实遍历了所有独特的路径，但我相信还有办法改进这个方法，以便真正打印出完整的路径。不知道为什么我找不到用递归来实现这个的方法。你们有什么想法吗？

Answer 1

到达那里有 (x+y)!/x!/y! （_x+yC_x）种方法。每个点的到达方式数量其实就是到达它旁边或下面的点的方式数量的总和。

Answer 2

是的，正如Bryan提到的，使用深度优先搜索（DFS）。在这种情况下，你不需要保留一个栈来记录你走过的路径，只需要一个计数器、一个位置和一个好的算法。

int count = 0;
int x = 0;
int y = 0;
int to_x[3] = {0, 0, 0};
for(; to_x[2] < 8; counter++)
{
    for(int arridx = 0; arridx < 2; arridx++)
    {
        if(to_x[arridx] == 8)
        {
            to_x[arridx] = 0;
            to_x[arridx+1] += 1;
        }
    }
/*
    for(int arridx2 = 0; arridx2 < 3; arridx2++)
    {
        //for(; x < to_x[arridx2]; x++);
        x = to_x[arridx2];

        y++;
    }
*/
}

这其实就是一个数学问题，但如果你不想让自己太头疼，就按照这个方法来做。

Answer 3

我建议你了解一下深度优先搜索和广度优先搜索。当x和y都大于3时，你的搜索就算成功了，而每条成功的搜索路径在树上都是有效的路径。