今日头条 2018 AI Camp 5 月 26 日在线笔试编程题第一道——最佳路径

题目

给定一个 n*m 的矩阵 A ，矩阵中每一个元素为一个十六进制数。寻找一条从左上角都右下角的路径，每次只能向右或者向下移动，
使得路径上所有数字之积在 16 进制下的后缀 0 最少。

输入描述：

第一行：n, m (2 <= n,m <= 1000)
接下来 n 行，每行 m 个 16 进制整数 0<=aij<=109 $0<=a_{ij}<={10}^9$

输出描述：

第一行：最少后缀 0 的个数(十进制)
第二行：路径方案，从左上角开始，”>” 代表向右移动，”V” 代表向下移动。
如果有多种方案，输出字典序最小的方案(“>” 的字典序小于 “V”)。

示例：

• 输入

  3 3
  3 2 8
  c 8 8
  2 a f

• 输出

  1
  ‘>>VV’(此处输出实际上没有引号)

• 说明
  从左上角到右下角的所有路径中， 0x3 * 0x2 * 0x8 * 0x8 * 0xf = 0x1680 后缀 0 最少为 1， 且路径 “>>VV” 的字典序最小。

思路

• 首先需要设计一个函数来判断十六进制数字末尾零的个数。可以分为两种情况，小于 16 的数只有 0 末尾有一个零；大于等于 16 的数如果最后一位是 0，则肯定可以被 16 整除，若末尾是 0，我们对这个十六进制数向右移一位，也即除以 16，再看倒数第二位是否是零，这样一直往前判断直到某一位非零为止。

• 路径判断则用动态规划来实现。定义两个变量，第一个变量保存从左上角到每一个位置处的乘积，第二个变量保存是怎样从前一步到当前位置的，只有向右或者向下两种情况，用枚举表示。第一行只能向右走，第一列只能向下走，这是初始化情况。然后从第二行第二列开始进行判断，每一步比较从左边来的乘积和从上边来的乘积末尾含有零的个数，若二者不相等，则保存乘积和移动方向到相应变量中。若向下和向右二者相等，则需要分别向上和向左回溯到左上角倒序求出移动方向，然后从头开始比较，选择字典序小的路径作为最终的移动方向。

样例展示 (从左到右分别是原始数字、十六进制乘积和移动方向)

第二行第二个位置，从左边来是 24×8 = 120，末尾有 1 个 0；从上边来是 6×8 = 30，也有 1 个 0。
从左边来路径是 V>，从右边来路径是 >V，由于 > 字典序小于 V，因此最终移动方向为 >V。

代码实现

#include <iostream>
#include <vector>
using namespace std;

int find_zero_num(int number);
int min_dictionary(int *direction, int i, int j, int col);
void find_route(int *direction, vector<int> &route, int m, int n, int col);

enum {RIGHT = 0, DOWN = 1}; //向下走为 1 ，向右走为 0

int main()
{
   int n = 0, m = 0;
   cin >> n >> m;

   int data[n][m];           
   //保存矩阵中的数据
   long int product[n][m];  
   //保存从左上角到位置(i, j)处的乘积
   int direction[n][m] = {0};
   //保存位置(i, j)处的乘积是怎么得到的，1为从前一位置往下，0为从前一位置往右

   vector<int> route; //倒序保存路径

   int i = 0, j = 0;

   for(i = 0; i < n ; i++)
   {
       for(j = 0; j < m; j++)
       {
           cin >> hex >> data[i][j];
       }
   }

   // 初始化第一列的乘积作为边界值
   product[0][0] = data[0][0];
   for(i = 1; i < n; i++)
   {
       product[i][0] = product[i-1][0] * data[i][0];
       direction[i][0] = DOWN;
   }

   // 初始化第一行的乘积作为边界值
   for(j = 1; j < m; j++)
   {
       product[0][j] = product[0][j-1] * data[0][j];
       direction[0][j] = RIGHT;
   }

   long int down = 0;
   long int right = 0;
   int flag = 0;

   for(i = 1; i < n; i++)
   {
       for (j = 1; j < m; j++)
       {
           down = product[i-1][j] * data[i][j]; //往下走的乘积
           right = product[i][j-1] * data[i][j]; //往右走的乘积

           if (find_zero_num(down) < find_zero_num(right))
           {
               flag = 1;
           }
           else if (find_zero_num(down) > find_zero_num(right))
           {
               flag = RIGHT;
           }
           else            //若向下和向右一样，则优先取字典序小的
           {
               if(min_dictionary(*direction, i, j, m))
               {
                   flag = DOWN;
               }
               else
               {
                   flag = RIGHT;
               }
           }

           if(!flag)
           {
               product[i][j] = right;
               direction[i][j] = RIGHT;
           }
           else
           {
               product[i][j] = down;
               direction[i][j] = DOWN;
           }
       }
   }

   cout << find_zero_num(product[n-1][m-1]) << endl;

   find_route(*direction, route, n-1, m-1, m);

   for(i = int(route.size()-1); i >= 0; i--)
   {
       if (route[i])
       {
           cout << 'V';
       }
       else
       {
           cout << '>';
       }
   }

   return 0;
}

// find the zero number of a hex data
int find_zero_num(int number)
{
   int sum = 0;
   if(number == 0)
   {
       sum = 1;
   }
   while (number % 16 == 0 && number >= 16)
   {
       sum++;
       number = number / 16;
   }
   return sum;
}

int min_dictionary(int *direction, int i, int j, int col)
{
   vector<int> route_down;
   vector<int> route_right;


   int m = i - 1;
   int n = j;
   find_route(direction, route_down, m, n, col); //向上回溯路线

   m = i;
   n = j - 1;
   find_route(direction, route_right, m, n, col); //向左回溯路线


   int length = int(route_right.size());

   for (i = length - 1; i >= 0; i--) //从第一个不相等的位置处开始判断字典序
   {
       if (route_right[i] < route_down[i])
       {
           return 0; //向右字典序小
       }
       if (route_right[i] > route_down[i])
       {
           return 1; //向下字典序小
       }
   }

   return -1;
}

// 从位置 (m, n) 处回溯路线，倒序保存在向量中
void find_route(int *direction, vector<int> &route, int m, int n, int col)
{
   while(1)
   {
       // 此位置乘积由上一位置向下移动得来，行数减一继续寻找
       if(direction[m * col + n] == 1)
       {
           m = m - 1;
           route.push_back(1);
       }
       // 此位置乘积由上一位置向右移动得来，列数减一继续寻找
       else
       {
           n = n - 1;
           route.push_back(0);
       }

       // 寻找至左上角，结束
       if (m == 0 && n == 0)
       {
           break;
       }
   }
}

个人见解，如有错误，欢迎指正与交流！

获取更多精彩，请关注「seniusen」!