问题 数组中等数之间的最大距离

除了迭代每一行，每一列和每个对角线之外，我不知道你怎么能更快地做到这一点（你可以通过获取其X和Y坐标的差值的绝对值来判断某些东西是否在同一对角线上当然）并跟踪您看到的每个数字的最新坐标，以及观察到的最大分离。

以下的主要思想是迭代数组一次，跟踪每行（hor），列（vert）和从上到下对角线（td）和从下到上对角线（dt）的最后找到的位置。有了这个，你只需找到每个方向到最后一个位置的距离并取最大值。

编辑： 另外一点，看起来问题是要求你弄清楚任何相同数字之间的最大距离，当我写出代码时我不明白。要解决这个问题，你只需要创建一个字典或数组（如果你知道可以存在的数字范围），为每个数字保存vert / hor / dt / td的集合，并使用那些而不是if yournum 。它仍然只需要一次通过阵列。

int findmax(int[,] myarray, int height, int width, int yournum)
{
int diagnum = width + height - 1;

int[] vert = new int[width];
int[] hor  = new int[height];

int[] td   = new int[diagnum];
int[] dt   = new int[diagnum];

for (int x = 0; x < width; x++)
{
   vert[x] = -1;
}
for (int x = 0; x < height; x++)
{
   hor[x] = -1;
}
for (int x = 0; x < diagnum; x++)
{
   td[x] = -1;
   dt[x] = -1;
}

int maxlen = 0;

for (int x = 0; x < width; x++)
{
   for (int y = 0; y < height; y++)
   {
      if (myarray[y,x] == yournum)
      {
         if (vert[x] == -1)
         {
            vert[x] = y;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(y - vert[x] - 1));
            vert[x] = y;
         }
         if (hor[x] == -1)
         {
            hor[x] = y;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(x - hor[y] - 1));
            hor[y] = x;
         }

         int tdcol = x - y + height - 1;
         int tdloc = Math.Abs(Math.Max(0, tdcol - height + 1) - x);
         if (td[tdcol] == -1)
         {
            td[tdcol] = tdloc;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(tdloc - td[tdcol] - 1));
            td[tdcol] = tdloc;
         }
         int dtcol = y + x;
         int dtloc = Math.Abs(Math.Max(0,dtcol-height+1) - x);
         if (dt[dtcol] == -1)
         {
            dt[dtcol] = dtloc;
         }
         else
         {
            maxlen = Math.Max(maxlen, Math.Abs(dtloc - dt[dtcol] - 1));
            dt[dtcol] = dtloc;
         }
      }
   }
}
return maxlen;
}

编辑 我仔细检查了方程式，但实际上没有尝试构建/测试代码，因此可能存在一些编译问题或逻辑问题，但似乎这应该可行。主要部分是使方程式正确，这使您可以绕过多次遍历数组（即每个方向一个）。

假设距离必须是两个相同数字之间的直接路径（即没有环形交叉口或无限循环）。

1. 创建一个10的数组（对于出现在问题中的数字）
   • DIGIT_STRUCT[10]
2. 为该数字的每个位置的每个数字创建一个数组。即采样整个网格并按编号排列。
   • DIGIT_STRUCT[n].POSTITIONS[]
3. 找出最大距离的那些位置的组合
   • 这是棘手的部分。但由于允许对角线移动，并且桌子是方形的，我相信你实际上可以按照距离原点（0,0）的距离对每个帖子进行排名。你只需挑选出第一次和最后一次出现（按排名）。它是一种排序，用于每个数字列表
   • DIGIT_STRUCT[n].MAX_DIST {POSITION a, POSITION b}
4. 确保每个至少有一条最小路径 MAX_DIST 存在而没有击中另一个位置编号。只有在整个行或列中填充了该数字时，才会阻止该路径。在你的 6 例如，整个列在子网格上被另一个6阻挡。
5. 比较每个数字的最大距离。

并非所有工作都需要在这里完成，您不需要验证明显会更短的路径。如果路径无效，则不需要搜索不同的位置组合（如果另一个数字包含相同的距离路径）。

如果你找到一个网格大小的潜在路径（在你的例子中是16），你应该尝试验证那个，因为没有其他人会更长。

验证路径应该需要两个子网格大小数组，hor和vert，为每个vert [x]添加一个数字，并为子网格内DIGIT_STRUCT中的每个POSTITION（x，y）添加一个hor [y]。如果不存在等于子网格大小的vert [n]或hor [m]，则您知道那里的最短路径将不会被阻止。

编辑

忘了路径可能不是最理想的。如果有这样的情况

0 0 1 1
1 0 1 1
1 0 0 0
1 1 1 0

这里的答案是0，路径= 6，从（0,0）到（3,3）

在这种情况下，您必须验证每个数字的路径，并且该验证应返回距离。因为路径的距离可能会增加，所以你必须为每个数字验证更多的路径（距离最多可能是两倍）。

问：你被迫走最直接的道路吗？在这种情况下（方形子网格），只有一个直接路径并且其被阻塞。如果你是你被迫这样做那么我认为你可以通过知道在验证过程中不会增加的路径来获得一些表现。

由于您正在寻找最长的“细分”，因此请使用最长的细分来开始搜索，然后使用较短的细分。从大端开始，只要找到具有匹配结束编号的段，就可以停止。这假设您只需返回一个更长或与任何其他段相等的单个段。