分享一个有趣的算法题

今天，在QQ群看到一个有趣的算法题，简单写了一下，本文做一个记录。

题目

做如下一个数据结构，给定N为行列数量（比如5）

然后给定索引X和Y，用以查询第X行，第Y列，然后将两个结果的元素相加（交叉的元素只需要加一次）即为结果。

分析

乍一看好像没有什么规律，但仔细看看便会发现，将表格中的元素位置依次相连起来，便得出了规律，从（0，0）下标开始算，每次相连起来的斜线上，每个点的下标之和都是一样的，只不过如果是横向增加则是右上斜向左下，然后到了纵向增加，然后方向又是左下斜向右上了。所以，我们只需要确定当前点位下标之和即可得到所有点位，然后反向做同样的操作即可得到下一条线

解题

根据上面分析出的规律，那就很容易写出代码如下

int n = 5;
int x = 1;
int y = 2;
int current=1;
bool rev=true;

int[,] nums = new int[n,n];

for(int l = 0; l < n + n - 1; l++){
    for(int a = 0; a <= l && a < n; a++){
        for(int b = 0; b <= l && b < n; b++){
            if(a + b == l){
                if(!rev){      
                    nums[a,b] = current;             
                }
                else{
                    nums[b,a] = current;
                }
                current++;
            }
        }
    }
    rev=!rev;
}

int[] xx = new int[n];
int[] yy = new int[n];

for(int a = 0; a < n; a++){
    xx[a] = nums[x-1,a];
}

for(int a = 0; a < n; a++){
    yy[a] = nums[a,y-1];
}

var result = xx.Concat(yy).Distinct().ToArray();

int sum=0;

foreach(var item in result){
   sum += item;
}

Console.WriteLine("数组为：");
Console.WriteLine(nums);
Console.WriteLine($"第{x}行，第{y}列结果为：");
Console.WriteLine(result);
Console.WriteLine($"结果为：{sum}");