应用在:算法可应用于俩点用一条直线连接,迷宫路径的最优解。求二维矩阵中权值最大路径。
算法思路:在矩阵路线遍历中,利用函数迭代,在上,下,左,右四个方向迭代,函数入栈时记录函数操作,退栈时恢复入栈的操作,在此过程中记录最优的迭代过程。
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
//定义矩阵中行与列坐标
typedef struct
{
int r;
int l;
}Node;
/*
* 路径结构体:
n:坐标数量
coordinate:节点坐标
*/
typedef struct
{
int n;
Node coordinate[];
}Path;
Path best_path;
Path temp_path;
//为矩阵申请储存空间
void initMatrix(int*** matrix, int m, int n)
{
*matrix = (int**)malloc(m*sizeof(int *));
for (int i = 0; i < m; i++)
{
(*matrix)[i] = (int *)malloc(n * sizeof(int));
}
}
//删除矩阵储存空间
void destoryMatrix(int*** matrix, int m, int n)
{
for (int i = 0; i < m; i++)
{
free((*matrix)[i]);
}
free(*matrix);
}
/*
* 递归遍历的函数
*/
void dfs(int** matrix,int i, int j, int m, int n)
{
//边界条件:(1)数组越界(2)“墙壁”或已走过
if (i < 0 || i >= m || j < 0 || j >= n || matrix[i][j] == 0)
{
return;
}
matrix[i][j] = 0;//该位置已走过标记为0
//临时路径中记录为1的连通
temp_path.coordinate[temp_path.n].r = i;
temp_path.coordinate[temp_path.n].l = j;
temp_path.n++;
//多条路径时best_path记录最大的temp_path
if (temp_path.n > best_path.n || best_path.n == 0)
{
memcpy(&best_path,&temp_path,sizeof(Path)+ temp_path.n*sizeof(Node));
}
//printf("temp_path.n=%d,i=%d,j=%d\n", temp_path.n, i, j);
//上,下,左,右全递归遍历
dfs(matrix,i - 1, j, m, n);//上
dfs(matrix,i + 1, j, m, n);//下
dfs(matrix,i, j - 1, m, n);//左
dfs(matrix,i, j + 1, m, n);//右
matrix[i][j] = 1;//该结点走不通时,恢复原场面
//临时路径中此节点置为0
temp_path.coordinate[temp_path.n].r = 0;
temp_path.coordinate[temp_path.n].l = 0;
temp_path.n--;
}
int getMaxLinked(int** matrix, int m, int n)
{
/*
* for循环遍历矩阵中数值为1的点
*在此尝试递归
*/
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (matrix[i][j] == 1)
{
//temp_path.n = 0;
//printf("temp_path.n = %d\n", temp_path.n);
dfs(matrix,i, j,m,n);
}
}
}
return 0;
}
void main()
{
int test_cout = 0;
int m, n = 0;
int** matrix = NULL ;
while (scanf_s("%d %d", &m, &n))
{
//printf("第%d次矩阵连通问题,", test_cout);
//printf("请输入矩阵行,列,具体矩阵值:\n");
//int rst;
//printf("%d,%d\n", m, n);
//输入矩阵初始化
initMatrix(&matrix, m, n);
temp_path.n = 0;
best_path.n = 0;
//输入矩阵值
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
scanf_s("%d", &matrix[i][j]);
}
}
//调试,打印矩阵
/*
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
printf("%d ", matrix[i][j]);
}
printf("\n");
}
*/
getMaxLinked(matrix, m, n);
//printf("%d\n", best_path.n);
for (int i = 0; i < best_path.n; i++)
{
printf("(%d,%d)\n", best_path.coordinate[i].r, best_path.coordinate[i].l);
}
memset(&best_path, 0, sizeof(Path) + best_path.n * sizeof(Node));
destoryMatrix(&matrix, m, n);
}
}