您的位置: 首页  >  文章  >  输出从矩阵左上角到右下角的所有路径

输出从矩阵左上角到右下角的所有路径

分类: 文章 • 2024-12-30 11:07:10

一、问题描述

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

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

1 2 3
4 5 6

二、解题思路

1、数学解法求路径数

(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的位置)，并进队列。

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

输出从矩阵左上角到右下角的所有路径

三、代码实现

[cpp] view plain copy
  1. #include <stdio.h>  
  2.   
  3. typedef struct temp  
  4. {  
  5.     int x;  
  6.     int y;  
  7.     int parent;  
  8. }Queue;  
  9.   
  10. void path(int m, int n)  
  11. {  
  12.     Queue q[1000];  
  13.     int front = 0, rear = 0, i;  
  14.   
  15.     q[rear].x = 0;  
  16.     q[rear].y = 0;  
  17.     q[rear++].parent = -1;  
  18.     while (front != rear)  
  19.     {  
  20.         if (q[front].x == m-1 && q[front].y == n-1)  
  21.         {  
  22.             i = front;  
  23.             while (i != -1)   
  24.             {  
  25.                 printf("%3d <-", q[i].x*n + q[i].y+1);  
  26.                 i = q[i].parent;  
  27.             }  
  28.             printf("\n");  
  29.         }  
  30.   
  31.         if (q[front].y < n-1)  
  32.         {  
  33.             q[rear].x = q[front].x;  
  34.             q[rear].y = q[front].y+1;  
  35.             q[rear++].parent = front;  
  36.         }  
  37.   
  38.         if (q[front].x < m-1)  
  39.         {  
  40.             q[rear].x = q[front].x+1;  
  41.             q[rear].y = q[front].y;  
  42.             q[rear++].parent = front;  
  43.         }  
  44.   
  45.         front++;  
  46.     }  
  47. }  
  48.   
  49. int main()  
  50. {  
  51.     path(3,4);  
  52.     return 0;  
  53. }  




https://blog.****.net/li_chong/article/details/8881924




相关推荐