阅读文本需要大概 8. 2 分钟
如有问题或建议,请公众号留言
题目
给定一个 n*m 的矩阵 A ,矩阵中每一个元素为一个十六进制数。寻找一条从左上角都右下角的路径,每次只能向右或者向下移动,使得路径上所有数字之积在 16 进制下的后缀 0 最少。
输入描述:
第一行:n, m (2
接下来 n 行,每行 m 个 16 进制整数
输出描述:
第一行:最少后缀 0 的个数(十进制)
第二行:路径方案,从左上角开始,">" 代表向右移动,"V" 代表向下移动。 如果有多种方案,输出字典序最小的方案(">" 的字典序小于 "V")。
示例:
输入
3 3
3 2 8
c 8 8
2 a f
输出
说明
从左上角到右下角的所有路径中, 0x3 * 0x2 * 0x8 * 0x8 * 0xf = 0x1680 后缀 0 最少为 1, 且路径 “>>VV” 的字典序最小。
思路
1.首先需要设计一个函数来判断十六进制数字末尾零的个数。可以分为两种情况,小于 16 的数只有 0 末尾有一个零;大于等于 16 的数如果最后一位是 0,则肯定可以被 16 整除,若末尾是 0,我们对这个十六进制数向右移一位,也即除以 16,再看倒数第二位是否是零,这样一直往前判断直到某一位非零为止。
2.路径判断则用动态规划来实现。定义两个变量,第一个变量保存从左上角到每一个位置处的乘积,第二个变量保存是怎样从前一步到当前位置的,只有向右或者向下两种情况,用枚举表示。第一行只能向右走,第一列只能向下走,这是初始化情况。然后从第二行第二列开始进行判断,每一步比较从左边来的乘积和从上边来的乘积末尾含有零的个数,若二者不相等,则保存乘积和移动方向到相应变量中。若向下和向右二者相等,则需要分别向上和向左回溯到左上角倒序求出移动方向,然后从头开始比较,选择字典序小的路径作为最终的移动方向。
样例展示(从左到右分别是原始数字、十六进制乘积和移动方向)
第二行第二个位置,从左边来是 24×8 = 120,末尾有 1 个 0;从上边来是 6×8 = 30,也有 1 个 0。
从左边来路径是 V>,从右边来路径是 >V,由于 > 字典序小于 V,因此最终移动方向为 >V。
代码实现
文章仅为个人见解,如有错误,欢迎交流与指正!
欢迎点赞和转发!
领取专属 10元无门槛券
私享最新 技术干货