演算法 - 售貨員旅行問題 (traveling salesman problem)

售貨員旅行問題是一種最佳化的問題，可以利用回溯或動態規劃來解決，在蔡宗翰譯的「演算法--使用C++虛擬碼」書中(碁峯資訊，2004年)，第六章「BRANCH-AND-BOUND」，分枝界限修剪法之最佳優先搜尋的方法能更快地解決問題。

在許多個城市中，售貨員必須節省他的時間走訪美一個城市去銷售他的物品，最後再回到原本的城市中，但城市與城市之災來回的時間不一樣，這可能是因為城市與城市之間的高速公路常常塞車，亦或是可能碰到一些單行道....等，所以依照時間的不確定性，找出一個最有效率的走法，這類問題稱之為售貨員旅行問題。

利用回溯，可先求出一段路徑作為比較基準，比之大就不再走下去，比之小就已它作為基準繼續再找更小的路徑，一直找到最後，最佳路徑即會出現，建構 TravelingSalesperson 類別傳入 W 陣列，W[i][j] 代表從城市 i 到城市 j 所花的時間，最後 bestPath 紀錄最佳路徑的走法，minlength 則是最佳路徑的時間長度，以下為 C# 範例程式碼：

class TravelingSalesperson
{
    int n;
    int[,] W;
    public int[] recordPath, bestPath;
    public int length, minlength;
    public TravelingSalesperson(int[,] W)
    {
        this.W = W;
        length = 0;
        minlength = int.MaxValue;
        n = W.GetLength(0);

        recordPath = new int[n];
        bestPath = new int[n];

        for (int i = 0; i < n; i++)
        {
            recordPath[i] = i;
            bestPath[i] = i;
        }
    }

    public void teavel(int i)
    {
        if (i > n - 1)
        {
            length += W[recordPath[n - 1], 0];
            if (length < minlength)
            {
                minlength = length;
                for (int k = 0; k < n; k++)
                    bestPath[k] = recordPath[k];
            }
            length -= W[recordPath[n - 1], 0];
            return;
        }

        for (int j = i; j < n; j++)
        {
            swapRecordPath(j, i);
            length += W[recordPath[i - 1], recordPath[i]];

            if (length < minlength)
                teavel(i + 1);

            length -= W[recordPath[i - 1], recordPath[i]];
            swapRecordPath(j, i);
        }
    }

    public void swapRecordPath(int i, int j)
    {
        int temp = recordPath[i];
        recordPath[i] = recordPath[j];
        recordPath[j] = temp;
    }
}

而分枝界限修剪法之最佳優先搜尋的方法，則提供 C# 原始碼，有興趣可以買書來參考，傳入 W 陣列，W[i][j] 代表從城市 i 到城市 j 所花的時間，minlength 則是傳入一個大於任何最佳解的數即可：

struct node
{
    public int level, bound;
    public string path;
    public bool[] isUse;
}

class Travel
{
    int[,] W;
    public node init;
    public int minlength;
    public string opttour;
    int num;

    public Travel(int[,] W, int minlength)
    {
        this.W = W;
        num = W.GetLength(0);

        init = new node();
        init.isUse = new bool[num];

        init.level = 0;
        init.path = "0";
        init.isUse[0] = true;
        init.bound = bound(init);

        this.minlength = minlength;
    }

    public void solve(node n)
    {
        List<node> PQ = new List<node>();
        node v = new node();
       

        if (n.bound < minlength)
        {
            if (n.level == num - 2)
            {
                int i;
                for (i = 0; n.isUse[i]; i++) ;
                n.path += string.Format(",{0}", i);

                int temp = length(n);
                if (temp < minlength)
                {
                    minlength = temp;
                    opttour = n.path;
                }

            }
            else
            {
                for (int i = 1; i < num; i++)
                {
                    if (n.isUse[i]) continue;


                    v.level = n.level + 1;
                    v.path = n.path + string.Format(",{0}", i);
                    v.isUse = new bool[num];
                    for (int j = 0; j < num; j ++)
                        v.isUse[j] = n.isUse[j];

                    v.isUse[i] = true;
                    v.bound = bound(v);

                    PQ.Add(v);
                    for (int j = PQ.Count - 1; j >= 1; j--)
                        if (PQ[j].bound < PQ[j - 1].bound)
                        {
                            node temp = PQ[j];
                            PQ[j] = PQ[j - 1];
                            PQ[j - 1] = temp;
                        }
                        else break;
                }
            }


            for (int i = 0; i < PQ.Count; i++)
                solve(PQ[i]);
        }
    }

    public int bound(node n)
    {
        int intBound = 0;
        int[] aIntPath = readPath(n.path);
        int intPathLen = aIntPath.Length;

        for (int i = 0; i < intPathLen - 1; i++)
            intBound += W[aIntPath[i], aIntPath[i + 1]];

        for (int i = 0; i < num; i++)
        {
            if (n.isUse[i] && i != aIntPath[intPathLen - 1]) 
                continue;

            int min = int.MaxValue;

            for (int j = 0; j < num; j++)
            {
                if (intPathLen > 1 && aIntPath[intPathLen - 1] == i 
                    && aIntPath[0] == j) continue;

                if (n.isUse[j] && j != aIntPath[0]) continue;

                if (i != j && W[i, j] < min)
                    min = W[i, j];
            }
            intBound += min;
        }
        aIntPath = null;
        return intBound;
    }

    public int length(node n)
    {
        int intLength = 0;
        int[] aIntPath = readPath(n.path);
        int intPathLen = aIntPath.Length;

        for (int i = 0; i < intPathLen - 1; i++)
            intLength += W[aIntPath[i], aIntPath[i + 1]];

        intLength += W[aIntPath[intPathLen - 1], aIntPath[0]];

        return intLength;
    }

    int[] readPath(string strPath)
    {
        string[] aStrPath = strPath.Split(new char[] { ',' },
            StringSplitOptions.RemoveEmptyEntries);

        int intPathLen = aStrPath.Length;

        int[] aIntPath = new int[intPathLen];
        for (int i = 0; i < intPathLen; i++)
            aIntPath[i] = Convert.ToInt32(aStrPath[i]);

        aStrPath = null;
        return aIntPath;
    }
}

回首頁

演算法 - 判斷是否為質數

利用以下 C# 程式碼中的 isPrime(int n) 可以找出 1 ~ 2147483647 之間的質數：

class Prime
{
    static int MAXSIZE = 46340;
    bool[] prime;
    int[] prime_table;
    int prime_table_len;

    public Prime()
    {
        prime_table_len = 0;
        prime = new bool[MAXSIZE + 1];
        prime_table = new int[MAXSIZE];
        initBoolArray(prime);

        for (int i = 3; i <= MAXSIZE; i += 2)
            if (prime[i])
            {
                for (int j = i + i; j <= MAXSIZE; j += i)
                    prime[j] = false;
                prime_table[prime_table_len++] = i;
            }
    }

    public bool isPrime(int n)
    {
        if (n == 2) return true;
        if (n % 2 == 0) return false;

        if (n <= MAXSIZE)
            return prime[n];

        for (int i = 0; i != prime_table_len && 
            prime_table[i] * prime_table[i] <= n; ++i)
            if (n % prime_table[i] == 0)
                return false;
        return true;
    }

    private void initBoolArray(bool[] value)
    {
        int len = value.Length;
        for (int i = 0; i < len; i ++ )
            value[i] = true;
    }
}

回首頁

演算法 - 最大公因數 ( 歐幾里得 )

最大公因數可以利用輾轉相除法求出，利用遞迴的方式，產生同於輾轉相除的作法，以下為 C# 程式碼範例：

public int gcd(int a, int b)
{                                                                
    if (a % b == 0){ return b;}                                                                       
    return gcd(b , a % b);                                                                            
}

回首頁

演算法 - 基數排序法 (radix sort )

基數排序(Radix sort)是一種排序演算法，它是這樣實現的：
將所有待比較數值(正整數)統一為同樣的數位長度,數位較短的數前面補零. 然後, 從最低位開始, 依次進行一次排序.這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列.
基數排序的方式可以採用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由鍵值的最右邊開始，而MSD則相反，由鍵值的最左邊開始。

時間複雜度：O(n log(r)m)( r 為基數， m 為堆數 )
空間複雜度：O(n * r)

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95

以下利用 C# 程式碼示範：

Queue[] qDigits;
public void sort(int[] s)
{
    int digit = 10, i;
    init(s);
    i = Convert.ToInt32(Math.Log10((s.Max() / 1.0)));

    i--; 
    while (i-- != 0)
        radix(ref digit);
}

public void init(int[] s)
{
    resetQueue();
    foreach (int i in s)
        qDigits[i % 10].Enqueue(i);
}

public void radix(ref int digit)
{
    Queue[] qTmp = qDigits;
    int digitTen = digit * 10;
    resetQueue();
    
    foreach (Queue q in qTmp)
    {
        while (q.Count != 0)
        {
            int i = Convert.ToInt32(q.Dequeue());
            qDigits[i % digitTen / digit].Enqueue(i);
        }
    }
    digit *= 10;
}

public void resetQueue()
{
    qDigits = new Queue[10];
    for (int i = 0; i < 10; i++)
        qDigits[i] = new Queue();
}

public void print()
{
    Console.Write("content: ");
    foreach (Queue q in qDigits)
    {
        while (q.Count != 0)
            Console.Write(q.Dequeue() + " ");
    }
}

回首頁

演算法 - 堆積排序法 (heap sort )

堆積排序（Heapsort）是指利用堆積樹（堆）這種資料結構所設計的一種排序演算法。堆積樹是一個近似完全二元樹的結構，並同時滿足堆積屬性：即子結點的鍵值或索引總是小於（或者大於）它的父節點。

時間複雜度：O(n logn)
空間複雜度：O(1)

通常堆積樹(heap)是通過一維陣列來實現的。在起始陣列為 0 的情形中：

堆積樹的根節點（即堆積樹的最大值）存放在陣列位置 1 的地方;

　　注意：不使用位置 0，否則左子樹永遠為 0[2]

父節點i的左子節點在位置 (2*i);
父節點i的右子節點在位置 (2*i+1);
子節點i的父節點在位置 floor(i/2);

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%A0%86%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

class Heap
{
    public int[] s;
    public int size;

    public Heap(int n, int[] s)
    {
        this.s = new int[n];
        for (int i = 0; i < n; i++)
            this.s[i] = s[i];
    }
}

class HeapSort
{
    public Heap h;

    public HeapSort(int n, int[] s)
    {
        h = new Heap(n, s);
    }

    public void sort(int n)
    {
        makeheap(n, h);
        removeKeys(n, h, h.s);
    }

    void siftdown(Heap tp, int i)
    {
        int parentIndex, lChildIndex, key;
        bool bFound;

        key = tp.s[i];
        parentIndex = i;

        bFound = false;
        
        while (leftNode(parentIndex) <= tp.size && !bFound)
        {
            if (leftNode(parentIndex) < tp.size &&
                tp.s[leftNode(parentIndex)] < tp.s[rightNode(parentIndex)])
                lChildIndex = rightNode(parentIndex);
            else
                lChildIndex = leftNode(parentIndex);

            if (key < tp.s[lChildIndex])
            {
                tp.s[parentIndex] = tp.s[lChildIndex];
                parentIndex = lChildIndex;
            }
            else
                bFound = true;
        }
        tp.s[parentIndex] = key;
    }

    int root(Heap tp)
    {
        int keyout;
        keyout = tp.s[0];
        tp.s[0] = tp.s[tp.size];
        tp.size = tp.size - 1;
        siftdown(tp ,0);
        return keyout;
    }

    void removeKeys(int n, Heap tp, int[] s)
    {
        int i;
        for (i = n - 1; i >= 0; i--)
            s[i] = root(tp);
    }

    void makeheap(int n, Heap tp)
    {
        int i;
        tp.size = (n - 1);
        for (i = (n - 1) / 2; i >= 0; i--)
            siftdown(tp, i);
    }

    int parentNode(int i)
    {
        return Convert.ToInt32(Math.Floor((i - 1) / 2.0));
    }

    int leftNode(int i)
    {
        return (2 * i + 1);
    }

    int rightNode(int i)
    {
        return (2 * i + 2);
    }
}

回首頁

演算法 - 快速排序法 (quick sort )

快速排序是一種排序演算法，由C. A. R. Hoare所發展的，以平均效能來說，排序 n 個項目要Θ(n log n)次比較。然而，在最壞的效能下，它需要Θ(n2)次比較。一般來說，快速排序實際上明顯地比其他Θ(n log n) 演算法更快，因為它的內部迴圈（inner loop）可以在大部分的架構上很有效率地被實作出來，且在大部分真實世界的資料，可以決定設計的選擇，減少所需時間的二次方項之可能性。

時間複雜度：最佳 - O(n logn)、最差 - O(n²)
空間複雜度：O(n logn)

快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
步驟為：

1.從數列中挑出一個元素，稱為 "基準"（pivot），
2.重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割結束之後，該基準就處於數列的中間位置。這個稱為分割（partition）操作。
3.遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞迴下去，但是這個演算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

public void sort(int l, int h, int[] s)
{
    int pivotIndex = 0;

    if (h > l)
    {
        quick(l, h, ref pivotIndex, s);
        sort(l, pivotIndex, s);
        sort(pivotIndex + 1, h, s);
    }
}

void quick(int l, int h, ref int pivotIndex, int[] s)
{
    int i, j, pivotItem;

    pivotItem = s[l];
    j = l;
    for (i = l + 1; i < h; i++)
    {
        if (s[i] < pivotItem)
        {
            j++;
            swap(ref s[i], ref s[j]);
        }
    }
    pivotIndex = j;
    swap(ref s[l], ref s[pivotIndex]);
}

void swap(ref int i, ref int j)
{
    int temp;
    temp = i;
    i = j;
    j = temp;
}

回首頁

演算法 - 合併排序法 ( merge sort )

合併排序（Merge sort)(另譯：歸併排序）是建立在歸併操作上的一種有效的排序演算法。該演算法是採用分治法（Divide and Conquer）的一個非常典型的應用。

歸併操作的過程如下：

1.申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
2.設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
3.比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指針到下一位置
4.重複步驟3直到某一指針達到序列尾
5.將另一序列剩下的所有元素直接複製到合併序列尾


時間複雜度：O(n logn)
空間複雜度：O(n)

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

public void sort(int n, int[] s)
{
    if (n > 1)
    {
        int left = n / 2, right = n - left;
        int[] l = new int[left];
        int[] r = new int[right];
        for (int i = 0; i < left; i++)
            l[i] = s[i];
        for (int i = 0; i < right; i++)
            r[i] = s[left + i];
        sort(left, l);
        sort(right, r);
        merge(left, right, l, r, s);
    }
}

void merge(int left, int right, int[] l, int[] r, int[] s)
{
    int i = 0, j = 0, k = 0;

    while (i < left && j < right)
    {
        if (l[i] < r[j])
        {
            s[k] = l[i];
            i++;
        }
        else
        {
            s[k] = r[j];
            j++;
        }
        k++;
    }
    if (i >= left)
        for (int m = j, c = 0; m < right; m ++, c ++)
            s[k + c] = r[m];
    else
        for (int m = i, c = 0; m < left; m ++, c ++)
            s[k + c] = l[m];
}

回首頁

演算法 - 選擇排序法 ( selection sort )

選擇排序(Selection sort)是一種簡單直觀的排序演算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小元素，然後放到排序序列末尾。以此類推，直到所有元素均排序完畢。

時間複雜度：O(n²)
空間複雜度：O(1)

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E9%81%B8%E6%93%87%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

public void sort(int n, int[] s)
{
    int i, j, flag;
    for (i = 0; i < n - 1; i++)
    {
        flag = i;
        for (j = i + 1; j < n; j++)
            if (s[j] < s[flag])
                swap(ref s[j], ref s[flag]);
    }
}

void swap(ref int i, ref int j)
{
    int temp;
    temp = i;
    i = j;
    j = temp;
}

回首頁

演算法 - 插入排序法 ( insertion sort )

插入排序（Insertion Sort）的演算法描述是一種簡單直觀的排序演算法。它的工作原理是通過構建有序序列，對於未排序數據，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，通常採用in-place排序（即只需用到O(1)的額外空間的排序），因而在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間。

時間複雜度：O(n²)
空間複雜度：O(1)

一般來說，插入排序都採用in-place在數組上實現。具體演算法描述如下：

1.從第一個元素開始，該元素可以認為已經被排序
2.取出下一個元素，在已經排序的元素序列中從後向前掃描
3.如果該元素（已排序）大於新元素，將該元素移到下一位置
4.重複步驟3，直到找到已排序的元素小於或者等於新元素的位置
5.將新元素插入到該位置中
6.重複步驟2

如果比較操作的代價比交換操作大的話，可以採用二分查找法來減少比較操作的數目。該演算法可以認為是插入排序的一個變種，稱為二分查找排序。

以上引用自維基百科：http://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F

以下利用 C# 程式碼示範：

public void sort(int n, int[] s)
{
    int i, j;
    int x;
    for (i = 1; i < n; i++)
    {
        x = s[i];
        j = i - 1;
        while (j >= 0 && s[j] > x)
        {
            s[j + 1] = s[j];
            j--;
        }
        s[j + 1] = x;
    }
}

回首頁

演算法 - 背包問題

背包問題在演算法中為一經典題型，是一種最佳化的問題，而解決最佳化的問題，就需要用到「動態規劃」來解決，它是利用遞迴特性來拼湊出最佳解答。

以下就用 ACM 624 作為範例題目( 中文翻譯 ACM 624 )，提供解法並且解釋它是如何解決問題。

input:
5 3 1 3 4
10 4 9 8 4 2
20 4 10 5 7 4
90 8 10 23 1 2 3 4 5 7
45 8 4 10 44 43 12 9 8 2

output:
1 4 sum:5
8 2 sum:10
10 5 4 sum:19
10 23 1 2 3 4 5 7 sum:55
4 10 12 9 8 2 sum:45

不過這裡將題目改一改，不是 CD 的問題，將 CD 改為背包，而每首歌的時間長度改為物品的公斤重，在背包最大限制重量下，最多能拿幾公斤。

以下為 C# 程式碼，首先需要宣告幾個全域變數：

static int[] item_kg_array; // 每件物品的公斤重
static bool[] record_item_isTake_array; // 紀錄臨時物品是否拿取
static bool[] best_item_isTake_array; // 紀錄最佳物品是否拿取
static int max_kg; // 背包公斤限制
static int item_count; // 物品數量
static int record_max_kg; // 紀錄目前最大公斤數

在程式開頭，讀取相關資料：

string line = Console.ReadLine();
string [] value = line.Split(new string[]{" "}, 
    StringSplitOptions.RemoveEmptyEntries );

max_kg = Convert.ToInt32(value[0]);
item_count = Convert.ToInt32(value[1]);

item_kg_array = new int[item_count];
record_item_isTake_array = new bool[item_count];
best_item_isTake_array = new bool[item_count];

for (int i = 2; i < item_count + 2; i++)
    item_kg_array[i - 2] = Convert.ToInt32(value[i]);

record_max_kg = 0;

接著就是重點程式碼，以下程式碼為一函式，函式傳入索引 index 與目前公斤重 now_kg，函式一開始就先判斷 now_kg 是否大於目前最大公斤重 record_max_kg 且 now_kg 小於背包公斤限制 max_kg，如果條件成立，則紀錄 record_max_kg 為 now_kg 且紀錄最佳拿取方式 best_item_isTake_array 為 record_item_isTake_array。
再來判斷 index 使否小於物品數量 item_count，如條件成立，則先將目前索引是否拿取設置成 true 後再次呼叫自己傳入索引值加 1 及目前公斤數加上物品在索引值位置的公斤重兩數，如不成立，將目前索引是否拿取設置成 false 後再次呼叫自己傳入索引值加 1 及目前公斤數。如此一來，程式就會像「二元樹」一樣，依照 index 索引值分別來展開拿與不拿此物品的樹，而答案就會呼之欲出了。

static void knapsack(int index, int now_kg)
{
    if (now_kg <= max_kg && now_kg > record_max_kg)
    {
        record_max_kg = now_kg;
        for (int j = 0; j < index; j++)
            best_item_isTake_array[j] = record_item_isTake_array[j];
    }
    if (index < item_count)
    {
        record_item_isTake_array[index] = true;
        knapsack(index + 1, now_kg + item_kg_array[index]);
        record_item_isTake_array[index] = false;
        knapsack(index + 1, now_kg);
    }
}

最後在主程式最後呼叫並且印出：

knapsack(0, 0);
for (int i = 0; i < item_count; i++)
    if (best_item_isTake_array[i]) Console.Write("{0} ", item_kg_array[i]);
Console.WriteLine("sum:{0}", record_max_kg);

回首頁

演算法 - 老鼠走迷宮

老鼠走迷宮為演算法中較基本的題型，給一迷宮圖形，畫出起點到終點的解法與解法數量，亦或是算出解法步數，都可以利用以下程式算出。

與大部分的演算法相同，老鼠走迷宮是利用遞迴的特性，使得老鼠能判斷上下左右是否有路，並且走到死路能回頭再找別的路走。
以下例子為左上走到右下的迷宮。
input:
8 7
..XXXXXX
X......X
X.X.XX.X
X.X.X..X
XXX.XXXX
X......X
XXXXXX..

output:
--XXXXXX
X---...X
X.X-XX.X
X.X-X..X
XXX-XXXX
X..----X
XXXXXX--

以C#為例子，用String.Split讀取 row 與 col：

string line = Console.ReadLine();
string[] value = line.Split(new string[]{" "}, 
          StringSplitOptions.RemoveEmptyEntries);
int col = Convert.ToInt32(value[0]);
int row = Convert.ToInt32(value[1]);

接著宣告一個 char 二維陣列，讀入迷宮的資料：

int eRowIndex = row - 1;
int eColIndex = col - 1;

char[,] maze = new char[row, col];
for (int i = 0; i < row; i++)
{
    char[] mazeTmp = Console.ReadLine().ToCharArray();
    for (int j = 0; j < mazeTmp.Length; j++)
        maze[i, j] = mazeTmp[j];
}
Console.WriteLine();

接下來是遞迴函式就是在模擬老鼠走法，每一步老鼠會做記號 ( 改為 '-' ) 並且判斷是否已經到了終點，如果未到終點，老鼠會嘗試上下左右是否有路，如果有路，接著往有路的方向呼叫函式；如果沒有路，就將此點記號取消 ( 改為 '.' )，如此一來，所有走到死路的走法都會回頭到岔路繼續往別的方向嘗試，最後，就會走到終點。

static void visit(int nRI, int nCI, int eRI, int eCI, char[,] maze)
{
    maze[nRI, nCI] = '-';
    if (nRI == eRI && nCI == eCI)
        print(maze);

    if (!(nRI - 1 < 0) && maze[nRI - 1,nCI] == '.') // 上
        visit(nRI - 1, nCI, eRI, eCI, maze);
    if (!(nCI - 1 < 0) && maze[nRI, nCI - 1] == '.') // 左
        visit(nRI, nCI - 1, eRI, eCI, maze);
    if (nRI + 1 <= eRI && maze[nRI + 1, nCI] == '.') // 下
        visit(nRI + 1, nCI, eRI, eCI, maze);
    if (nCI + 1 <= eCI && maze[nRI, nCI + 1] == '.') // 右
        visit(nRI, nCI + 1, eRI, eCI, maze);

    maze[nRI, nCI] = '.';
}

static void print(char[,] maze)
{
    for (int i = 0; i < maze.GetLength(0); i++)
    {
        for (int j = 0; j < maze.GetLength(1); j++)
            Console.Write(maze[i, j]);
        Console.WriteLine();
    }
    Console.WriteLine();
}

最後，只要傳入起點位置與終點位置與迷宮陣列，即能將解法輸出：
visit(0, 0, eRowIndex, eColIndex, maze);

回首頁