移山之道

问题

假设有4×4的方阵（里面可放字符串），给现定一个序列，检查这个序列是否在方阵的“连续对角线”上面：

例如：从左上到右下的连续对角线序列可能是：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16

分析

刚刚看到此题目，可能有点晕，“连续对角线”是啥？仔细一看，其实就是方阵里面的曲线序列（如下图），我就叫它“方曲序列”吧。

再一想，这样的序列应该有8条。考试的时候时间紧，只能大概写写思路了，回来用VS08调试着搞感觉好很多:( 不适合应试哈哈

我们来分析下，这个题目的关键是，要把握住曲线运动其实是两个方向：

1. 沿斜线运动
2. 斜线平移

那么，再看这些斜线的长度分别为 1 2 3 4 3 2 1，那么我们在枚举到这个序列之和的这些关键带点的时候：

1. 需要平移斜线
2. 需要翻转斜线上的运动方向

解法

有了思路，借助VS08 强大的调试功能，我写了8个方向，通用的，O(N)（N是序列长度） 复杂度的 “方曲序列” 函数：

运行函数：PrintWinding(4);

就可以得到 n=4 的时候8条“方曲序列”：

1 2 5 9 6 3 4 7 10 13 14 11 8 12 15 16
13 14 9 5 10 15 16 11 6 1 2 7 12 8 3 4
4 3 8 12 7 2 1 6 11 16 15 10 5 9 14 13
16 15 12 8 11 14 13 10 7 4 3 6 9 5 2 1
1 5 2 3 6 9 13 10 7 4 8 11 14 15 12 16
13 9 14 15 10 5 1 6 11 16 12 7 2 3 8 4
4 8 3 2 7 12 16 11 6 1 5 10 15 14 9 13
16 12 15 14 11 8 4 7 10 13 9 6 3 2 5 1

代码如下：

        static void PrintWinding(int n)
        {
            var square = new string[n, n];
            for (int i = 0; i < square.Length; i++)
                square[i / n, i % n] = (i + 1).ToString();

            var p = new int[] { 0, n - 1 };
            for (int sign = -1; sign <= 1; sign += 2)
                for (int i = 0; i < p.Length; i++)
                    for (int j = 0; j < p.Length; j++)
                        PrintWinding(square, p[ i], p[j], sign);
        }

其中：

        static void PrintWinding(string[,] square, int x0, int y0, int sign)
        {
            int n = square.GetLength(0);//边长

              int xn = Math.Abs(x0 - n + 1);//目标点x
            int yn = Math.Abs(y0 - n + 1);//目标点y

            int dx = Math.Sign(xn - x0);//平移方向x增量
             int dy = Math.Sign(yn - y0);//平移方向y增量

             int stepX = -dx * sign;//斜线方向x增量
             int stepY = dy * sign;//斜线方向y增量

             int flag = sign == 1 ? 0 : 1;

            int x = x0, y = y0;
            int s = 1, k = 1, sum = 1;
            for (int i = 0; i < square.Length; i++)
            {
                Console.Write(square[y, x] + " ");

                if (i + 1 < sum)
                {
                    x += stepX;
                    y += stepY;//沿斜线方向移动
                  }
                else if (i + 1 == sum)
                {
                    stepX *= -1;
                    stepY *= -1;//斜线方向掉头

                      if (k == n) flag = Math.Abs(1 - flag);

                   if ((k & 1) == flag) x += dx;//平移
                      else y += dy;//平移

                     if (s < n) k++;//前半三角
                     else k--;//后半三角

                     sum += k;
                   s++;
                }
            }
            Console.WriteLine();
        }

讨论

有了8个方向，通用的“方曲序列” 函数，我们就不难写出测试某序列是否在”连续对角线“上面的函数了，可以考虑采用PLINQ写个并行算法，多个核的话每个核测试一个（些）方向的序列，找到就返回true。