Преобразование кода C ++ в C # для гамильтонова алгоритма пути - PullRequest
Новая
       51

Преобразование кода C ++ в C # для гамильтонова алгоритма пути

0 голосов
/ 06 февраля 2019

Я пытаюсь продублировать часть 2 урока на по этой ссылке в C #.Я написал код, и он компилируется, но функция всегда возвращает false.Для этой задачи я заполнил четыре узла, расположенных в виде сетки с размерами 2x2.Узлы связаны с узлами справа, слева, вверх или вниз, и каждый узел представлен как arr [i] [j], где «i» - это строка, а «j» - это столбец.

Вот код: 

static int length = 2;
    static int MAXN = length * length;


    static void Main(string[] args)
    {
        var arr = InitArray();
        bool check = CheckUsingDP(arr, length);
    }


    public static int[,] InitArray()
    {
        var n = length;
        var arr = new int[n * n, n * n];

        for (var j = 0; j < n * n; j++)
        {
            for (var i = 0; i < n * n; i++)
            {
                if (arr[i, j] != 1 && i != j)
                {
                    arr[i, j] = 0;
                    if (i > 0 && (i % n - j % n == 0 || (Math.Abs(i % n - j % n) == 1 && i / n == j / n)) && Math.Abs(i - j) <= n)
                    {
                        arr[i, j] = 1;
                        arr[j, i] = 1;
                    }
                    if (j > 0 && (j % n - i % n == 0 || (Math.Abs(i % n - j % n) == 1 && i / n == j / n)) && Math.Abs(i - j) <= n)
                    {
                        arr[i, j] = 1;
                        arr[j, i] = 1;
                    }
                }
            }
        }

        return arr;
    }

    static bool CheckUsingDP(int[,] adj, int n)
    {

        bool[,] dp = new bool[MAXN, 1 << MAXN];
        for (int i = 0; i < n; i++)
            dp[i, 1 << i] = true;
        for (int i = 0; i < (1 << n); i++)
        {
            for (int j = 0; j < n; j++)
                if ((i & (1 << j)) == 1)
                {
                    for (int k = 0; k < n; k++)
                        if (((i & (1 << k)) == 1) && adj[k, j] == 1 && k != j && dp[k, i ^ (1 << j)])
                        {
                            dp[j, i] = true;
                            break;
                        }
                }
        }
        for (int i = 0; i < n; i++)
            if (dp[i, (1 << n) - 1])
                return true;

        return false;
    }
...