一、问题描述

一个m×n的矩阵，只能从矩阵内部向右或向下走，输出从矩阵左上角到右下角的所有路径。

下图即为从1到6的所有路径

二、解题思路

(1)使用排列组合。因为只能向右走或者向下走，在(m-1)+(n-1)次行走后，才能到达终点，也就是右下角。而在这m+n-2次行走中，有m-1次是向下，n-1次向右，所以是一个选择问题：

(2)水平行走记作0，竖直行走记作1。每一种行走足迹可以作为一个0,1串，其中n-1个0，m-1个1。可以看做0000000000000（n-1个0）1111111111111（m-1个1）的重排列，也就是：

2、队列输出所有路径

用队列实现打印所有路径。用结构体表示队列中每个点的状态(坐标值及其父结点，初始结点的父结点为-1)，开始初始结点(根结点)进队列，然后循环执行以下操作直到队列为空：

1)结点Q出队列。

2)判断Q是否到达目标结点(叶节点)，若到达，则依据每个结点的父结点，输出从叶结点到根结点的这条路径。

3)若Q的右结点和下结点未出边界，则记录其父结点的位置(即Q的位置)，并进队列。

输出可以看做是一棵二叉树从根结点到叶结点的所有路径。

三、代码实现