解决二维矩阵中最大连通路径

应用在:算法可应用于俩点用一条直线连接,迷宫路径的最优解。求二维矩阵中权值最大路径。

算法思路:在矩阵路线遍历中,利用函数迭代,在上,下,左,右四个方向迭代,函数入栈时记录函数操作,退栈时恢复入栈的操作,在此过程中记录最优的迭代过程。

#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);
	}
			
}

上一篇:极速办公Word文档的查找和替换功能键在哪?


下一篇:机器学习最困难的部分:超参数调试