c# - 如何根据 C# 中单元格的特定值对矩形数组进行排序

Question

我有一个由 0 和 1 组成的矩形数组。我需要获得一个由这些索引组成的路径。我需要获得最好的路径，即从起点可以相互连接的路径数量最长的最佳路径。路径是一组可以相互连接的路径:垂直、水平或对角线，您可以使用所有这些方向移动。

Answer 1

您可以使用简单的递归算法来遍历整个数组。对于该函数的每次调用，您都会得到一个您已经访问过的单元格列表(“路径”)和您刚刚输入的当前单元格。

您将当前单元格添加到列表中，并在您所在的单元格周围查看不在路径列表中的任何“1”单元格。

如果您周围没有不在路径列表中的“1”单元格，则返回路径列表。

如果您周围确实有“1”个您尚未访问过的单元格，请使用您目前拥有的路径在每个单元格上递归使用您的函数，按长度比较它们的返回结果路径，并返回最长的路径。

添加了代码示例:

        using System;
        using System.IO;
        using System.Text;
        using System.Drawing;
        using System.Collections;
        using System.ComponentModel;
        using System.Windows.Forms;
        using System.Data;
        using System.Threading;
        using AUV_Topology;
        using System.Collections.Generic;
        using System.Media;
        using System.Linq;

        namespace AUVtopology
        {
            public partial class Form1 : Form
            {        
              static int[,] array;
              static List<int[]> path;
        //This method is used to make sure the coordinate array 
        //is contained in the list. List.contains(new int[] {val1,val2}) was not enough.
        static Boolean containsArray(List<int[]> list, int[] array)
        {
            if (array == null || array.Length == 0)
            {
                return false;
            }
            foreach (var listArray in list)
            {
                if (listArray != null && listArray.Length == array.Length)
                {
                    for (int i = 0; i < listArray.Length; i++)
                    {
                        if (array[i] != listArray[i])
                        {
                            continue;
                        }
                        return true;
                    }
                    return false;
                }
            }
            return false;
        }    

        //This is the recursive method of the algorithm. It finds the 
        //maximum path of 1 cells in a matrix of 0/1 cells
        static List<int[]> getMaxPath(int[,] array, List<int[]> maxPath, int rowIndex, int colIndex)
        {  
                 //End case in which we started (or ended up) in a 0 cell
                 if (array[rowIndex,colIndex] != 1) {
                     return maxPath;
                 }

                 //if we back-tracked and this cell was visited
                 if (containsArray(maxPath, new int[]{rowIndex,colIndex})) {
                     return maxPath;
                 }

                 //Add the current cell to the path.
                 maxPath.Add(new int[]{rowIndex,colIndex});

                 //Get the array limits.
                 int rowLength = array.GetLength(0);
                 int colLength = array.GetLength(1);

                 //If the path contains all the cells in the matrix, stop
                 if (maxPath.Count >= rowLength * colLength) {
                     return maxPath;
                 }

                 //remove one from lengths to make it the maximum index
                 colLength = colLength - 1;
                 rowLength = rowLength - 1;

                 //We'll use this variables to see which of the 
                 //potential 7 paths is the longest.
                 List<int[]> futurePath;

                 //Go over all 8 possible adjoining cells:
                 //If we can go one down, one right
                 if (colIndex < colLength && rowIndex < rowLength) {

                        //We use maxPath first, since this is the first 
                        //direction and by default is the longest
                        maxPath = getMaxPath (array, maxPath, rowIndex+1, colIndex+1);
                 } 

                 //If we can go one down
                 if (colIndex < colLength) {

                       //We use futurePath now, since this is a second
                       //direction and a potential contender
                       futurePath = getMaxPath (array, maxPath, rowIndex, colIndex+1);

                      //We only need the maximum path.
                      if (futurePath.Count > maxPath.Count) {
                          maxPath = futurePath;
                      }
                 } 

                 //If we can go one down and one left
                 if (rowIndex>0 && colIndex < colLength) {

                         futurePath = getMaxPath (array, maxPath, rowIndex-1, colIndex+1);
                         if (futurePath.Count > maxPath.Count) {
                             maxPath = futurePath;
                         }
                 }

                 //If we can go one left
                 if (rowIndex>0) {

                         futurePath = getMaxPath (array, maxPath, rowIndex-1, colIndex);
                         if (futurePath.Count > maxPath.Count) {
                             maxPath = futurePath;
                         }
                 }
                 //If we can go one left and one up
                 if (rowIndex>0 && colIndex>0) {

                     futurePath = getMaxPath (array, maxPath, rowIndex-1, colIndex-1);
                     if (futurePath.Count > maxPath.Count) {
                          maxPath = futurePath;
                     }
                 }                 
                 //If we can go one up
                 if (colIndex>0) {

                         futurePath = getMaxPath (array, maxPath, rowIndex, colIndex-1);
                         if (futurePath.Count > maxPath.Count) {
                             maxPath = futurePath;
                         }
                 }
                 //If we can go one up and one right
                 if (colIndex>0 && rowIndex < rowLength) {

                    futurePath = getMaxPath (array, maxPath, rowIndex+1, colIndex-1);
                    if (futurePath.Count > maxPath.Count) {
                         maxPath = futurePath;
                    }
                 }
                 //If we can go one right
                 if (rowIndex < rowLength) {

                     futurePath = getMaxPath (array, maxPath, rowIndex+1, colIndex);
                     if (futurePath.Count > maxPath.Count) {
                         maxPath = futurePath;
                     }
                 }

                //We return the max path. Note: If none of the directions around 
                //us was applicable, we simply return the path we started 
                //with with our cell included.
                return maxPath;
          }