回溯法及其应用

╰半夏微凉° 2022-09-30 06:11 151阅读 0赞

参考链接：

1.  [http://www.cnblogs.com/chinazhangjie/archive/2010/10/22/1858410.html][http_www.cnblogs.com_chinazhangjie_archive_2010_10_22_1858410.html]
2.  [http://baike.baidu.com/link?url=m-I1xz9PSYf9Hr8koWBcx2JNnHVCmKT\_wA4L4ryrqHocN-I6oTp-pnEl9HB3FhhT8Gr2J50mG-aNRmF6K5QHbnO3\_GdQOFM7lxBvUUc0zfOnDVhjvNEToqqY8Xeng9zC][http_baike.baidu.com_link_url_m-I1xz9PSYf9Hr8koWBcx2JNnHVCmKT_wA4L4ryrqHocN-I6oTp-pnEl9HB3FhhT8Gr2J50mG-aNRmF6K5QHbnO3_GdQOFM7lxBvUUc0zfOnDVhjvNEToqqY8Xeng9zC]

### 一、回溯法原理 ###

回溯法（探索与回溯法）是一种选优探索法，又称为试探法，按选优条件向前探索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术称为回溯法，而满足回溯条件的某个状态的点成为“回溯点”。

**基本思想：**  
在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度搜索解空间树。当探索到某一节点时，要先判断该节点是否包含问题的解，如果包含，就从该节点出发继续探索下去，如果该节点不包含问题的解，则逐层向其祖先节点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根节点的所有可行的子树都要已被搜索遍才结束。而若使用回溯法求任一个可行解时，只要搜索到问题的一个解就可以结束。

**思想阐述：**  
可用回溯法求解的问题P，通常要能表达为：对于已知的由n元组（x1，x2，…，xn）组成的一个状态空间E=\{（x1，x2，…，xn）∣xi∈Si ，i=1，2，…，n\}，给定关于n元组中的一个分量的一个约束集D，要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域，且 |Si| 有限，i=1，2，…，n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。

解问题P的最朴素的方法就是**枚举法**，即对E中的所有n元组逐一地检测其是否满足D的全部约束，若满足，则为问题P的一个解。但显然，其计算量是相当大的。

回溯法与枚举法的不同在于回溯法可以利用约束条件或限界条件剪枝。回溯法从根节点开始按深度优先搜索策略形成的树成为状态空间树，状态空间树中的每一个节点成为状态节点，每一个叶子节点成为解状态节点，每一个满足所有约束条件或限界条件的叶子节点成为回答状态节点，对应问题的一个解。回溯法在进行深度优先搜索时到达一个状态节点，如果其不满足约束条件或限界条件，那么这个状态节点继续往下深度优先搜索的所有状态也都不会满足约束条件，因此这个状态节点以后的状态节点都不用再考虑，这就是利用约束条件或限界条件进行剪枝的原理，也是回溯法相比枚举法减少计算复杂度的方法。

**回溯法解题的一般步骤：**

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

注意每次进行回溯时一定要恢复当前状态节点的状态。比如状态节点 v 有两个子节点 x 和 y， 从状态节点v出发深度优先搜索子节点 x ，当 x及其子孙节点搜索完毕回溯到状态节点 v 时， 需要将遍历 x 子孙节点时改变的状态都还原至 v 时的状态。

### 二、回溯法应用 ###

1.01背包问题。

01背包问题描述：有编号分别为a,b,c,d,e的五件物品 n=5，它们的重量分别是w1=2,w2=2,w3=6,w4=5,w5=4，它们的价值分别是v1=6,v2=3,v3=5,v4=4,v5=6，每件物品数量只有一个，现在给你个承重为C=10的背包，如何让背包里装入的物品具有最大的价值总和？

01背包问题更常用的解法是动态规划算法，其时间复杂度为 O(nC), 空间复杂度为O(nC)，动态规划算法解决01背包问题解法详细描述参见：[http://blog.csdn.net/na\_beginning/article/details/62884939][http_blog.csdn.net_na_beginning_article_details_62884939]

这里我们使用回溯法也可以解决01背包问题，首先定义问题解空间，从物品 a 开始考虑，存在两种选择，背包放入 a （用1做标记）和不放入 a （用 0 做标记），然后一次考虑其他四件物品，分别都有两种选择，放入和不放入，可以构建一个子集树，这棵树就是状态空间树，每一条从根节点 a 到叶子结点的路径构成了解空间。按深度优先策略从根节点 a 搜索整棵树，先考虑放入的情况，再考虑不放入的情况，没达到一个状态都需要判断当前状态中是否满足约束条件—当前背包中已放入物品的总重量是否超过背包能容纳的重量 C，如果不满足约束条件就回溯，回溯时要注意一定要恢复状态。

回溯法解决01背包问题的时间复杂度是 O(2^n), 因为每一件物品都需要考虑放入与不放入两种情况，实际复杂度会比这个小，因为中间状态不满足约束条件时存在剪枝；空间复杂度是O(n)，因为递归需要用到栈，栈的深度是O(n)，即空间搜索树的高度，而且保存搜索路径时也需要用到O(n)长度的数组。

代码：

#include <iostream>
    using namespace std;
    
    
    void knapsack_backtrack(int layer, int n, int *W, int *V, int C, int currentWeight, int currentValue, int *path, int *best, int &bestV)
    {
        if(layer > n)
        {
            if(currentValue > bestV && currentWeight <= C)
            {
                bestV = currentValue;
                for(int i = 0; i < n; i++)
                {
                    best[i] = path[i];
                }
            }
            return;
        }
        if(currentWeight > C)
            return;
        if(currentWeight + W[layer-1] <= C)
        {
            currentWeight += W[layer-1];
            path[layer-1] = 1;
            currentValue += V[layer-1];
            knapsack_backtrack(layer+1, n, W, V, C, currentWeight, currentValue, path, best, bestV);
            currentWeight -= W[layer-1];
            currentValue -= V[layer-1];
        }
        path[layer-1] = 0;
        knapsack_backtrack(layer+1, n, W, V, C, currentWeight, currentValue, path, best, bestV);
    }
    
    void test1()
    {
        int n, C;
        while(cin >> n >> C)
        {
            int *W = new int[n];
            int *V = new int[n];
            int *best = new int[n];
            for(int i = 0; i < n; i++)
            {
                cin >> W[i] >> V[i];
            }
            int *path = new int[n];
            int currentWeight = 0, currentValue = 0;
            int bestV = 0;
            knapsack_backtrack(1, n, W, V, C, currentWeight, currentValue, path, best, bestV);
            for(int i = 0; i < n; i++)
            {
                cout << best[i] << " ";
            }
            cout << endl;
            cout << bestV << endl;
            delete path; path = 0;
            delete best; best = 0;
            delete V; V = 0;
            delete W; W  = 0;
        }
    }
    int main()
    {
        test1();
        return 0;
    }

输入示例：

5 10       //5件物品 n = 5，背包容量为 C = 10
    2 6        //第一件物品， 重量为 2, 价值为 6
    2 3
    6 5
    5 4
    4 6

输出示例：

1 1 0 0 1   //1表示放入一件物品，0表示不放入
    15          // 放入第一件、第二件、第五件物品价值最大，1*6 + 1*3 + 0*5 + 0*4 + 1*6 = 15

2.八皇后问题

八皇后问题描述：八皇后问题是一个古老而著名的问题。该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一对角线上，问有多少种摆法。

问题分析：8\*8的棋盘，放入8个皇后，按照皇后的放置规则，如果存在可行解，那么必然棋盘每一行都有一个皇后，而且它们不同列。按照这个结论，我们可以一行行地进行考虑，先考虑第一行放置第一个皇后，从第 1 列依次考虑到第 8 列，如果满足皇后放置规则（两皇后不同行不同列不在同一对角线），那么先考虑把皇后放在该位置继续深度优先搜索，并记录该皇后在第一行放置的位置，深度搜索完之后，恢复第一行状态，即抹除记录的第一行放置位置，继续考虑第一行的其他位置，依次进行，直到一直考虑到第8行或者存在某一行不能放置皇后为止。可以看出在利用回溯法解决八皇后问题时，解空间就是从第一行到第八行逐行考虑放置皇后的位置，如果存在能在第八行放置皇后，那么就存在一个可行解。每个状态节点记录的状态就是当前行放置皇后在第几列，这个状态在回溯时需要抹除。

代码：

#include <iostream>
    using namespace std;
    
    
    bool is_seat(int *row, int *col, int n, int a, int b)
    {
        int i = a, j = b;
        if(row[i] != -1 || col[j] != -1)
            return false;
        while(i >= 0 && j >= 0)
        {
            if(row[i] == j)
                return false;
            i--;
            j--;
        }
        i = a; j = b;
        while(i >= 0 && j < n)
        {
            if(row[i] == j)
                return false;
            i--;
            j++;
        }
        return true;
    }
    
    void eightQueen(int layer, int *row, int *col, int n, int &num)
    {
        if(layer > n)
        {
            bool flag = true;
            for(int i = 0; i < n; i++)
            {
                if(row[i] == -1)
                    flag = false;
            }
            if(flag)
            {
                num++;
                for(int i = 0; i < n; i++)
                {
                    cout << "(" << i+1 << ", " << row[i]+1 << ")" << " ";
                }
                cout << endl;
            }
            return;
        }
        for(int i = 0; i < n; i++)
        {
            if(is_seat(row, col, n, layer-1, i))
            {
                row[layer-1] = i;
                col[i] = layer-1;
                eightQueen(layer+1, row, col, n, num);
                row[layer-1] = -1;
                col[i] = -1;
            }
        }
    }
    void test1()
    {
        int row[8];
        int col[8];
        for(int i = 0; i < 8; i++)
        {
            row[i] = -1;
            col[i] = -1;
        }
        int num = 0;
        eightQueen(1, row, col, 8, num);
        cout << num << endl;
    }
    
    int main()
    {
        test1();
        return 0;
    }

输出示例：（每一行表示一个可行解，放置的8个皇后在棋盘中的位置，最后一行为可行解的个数）

(1, 1) (2, 5) (3, 8) (4, 6) (5, 3) (6, 7) (7, 2) (8, 4) 
    (1, 1) (2, 6) (3, 8) (4, 3) (5, 7) (6, 4) (7, 2) (8, 5) 
    (1, 1) (2, 7) (3, 4) (4, 6) (5, 8) (6, 2) (7, 5) (8, 3) 
    (1, 1) (2, 7) (3, 5) (4, 8) (5, 2) (6, 4) (7, 6) (8, 3) 
    (1, 2) (2, 4) (3, 6) (4, 8) (5, 3) (6, 1) (7, 7) (8, 5) 
    (1, 2) (2, 5) (3, 7) (4, 1) (5, 3) (6, 8) (7, 6) (8, 4) 
    (1, 2) (2, 5) (3, 7) (4, 4) (5, 1) (6, 8) (7, 6) (8, 3) 
    (1, 2) (2, 6) (3, 1) (4, 7) (5, 4) (6, 8) (7, 3) (8, 5) 
    (1, 2) (2, 6) (3, 8) (4, 3) (5, 1) (6, 4) (7, 7) (8, 5) 
    (1, 2) (2, 7) (3, 3) (4, 6) (5, 8) (6, 5) (7, 1) (8, 4) 
    (1, 2) (2, 7) (3, 5) (4, 8) (5, 1) (6, 4) (7, 6) (8, 3) 
    (1, 2) (2, 8) (3, 6) (4, 1) (5, 3) (6, 5) (7, 7) (8, 4) 
    (1, 3) (2, 1) (3, 7) (4, 5) (5, 8) (6, 2) (7, 4) (8, 6) 
    (1, 3) (2, 5) (3, 2) (4, 8) (5, 1) (6, 7) (7, 4) (8, 6) 
    (1, 3) (2, 5) (3, 2) (4, 8) (5, 6) (6, 4) (7, 7) (8, 1) 
    (1, 3) (2, 5) (3, 7) (4, 1) (5, 4) (6, 2) (7, 8) (8, 6) 
    (1, 3) (2, 5) (3, 8) (4, 4) (5, 1) (6, 7) (7, 2) (8, 6) 
    (1, 3) (2, 6) (3, 2) (4, 5) (5, 8) (6, 1) (7, 7) (8, 4) 
    (1, 3) (2, 6) (3, 2) (4, 7) (5, 1) (6, 4) (7, 8) (8, 5) 
    (1, 3) (2, 6) (3, 2) (4, 7) (5, 5) (6, 1) (7, 8) (8, 4) 
    (1, 3) (2, 6) (3, 4) (4, 1) (5, 8) (6, 5) (7, 7) (8, 2) 
    (1, 3) (2, 6) (3, 4) (4, 2) (5, 8) (6, 5) (7, 7) (8, 1) 
    (1, 3) (2, 6) (3, 8) (4, 1) (5, 4) (6, 7) (7, 5) (8, 2) 
    (1, 3) (2, 6) (3, 8) (4, 1) (5, 5) (6, 7) (7, 2) (8, 4) 
    (1, 3) (2, 6) (3, 8) (4, 2) (5, 4) (6, 1) (7, 7) (8, 5) 
    (1, 3) (2, 7) (3, 2) (4, 8) (5, 5) (6, 1) (7, 4) (8, 6) 
    (1, 3) (2, 7) (3, 2) (4, 8) (5, 6) (6, 4) (7, 1) (8, 5) 
    (1, 3) (2, 8) (3, 4) (4, 7) (5, 1) (6, 6) (7, 2) (8, 5) 
    (1, 4) (2, 1) (3, 5) (4, 8) (5, 2) (6, 7) (7, 3) (8, 6) 
    (1, 4) (2, 1) (3, 5) (4, 8) (5, 6) (6, 3) (7, 7) (8, 2) 
    (1, 4) (2, 2) (3, 5) (4, 8) (5, 6) (6, 1) (7, 3) (8, 7) 
    (1, 4) (2, 2) (3, 7) (4, 3) (5, 6) (6, 8) (7, 1) (8, 5) 
    (1, 4) (2, 2) (3, 7) (4, 3) (5, 6) (6, 8) (7, 5) (8, 1) 
    (1, 4) (2, 2) (3, 7) (4, 5) (5, 1) (6, 8) (7, 6) (8, 3) 
    (1, 4) (2, 2) (3, 8) (4, 5) (5, 7) (6, 1) (7, 3) (8, 6) 
    (1, 4) (2, 2) (3, 8) (4, 6) (5, 1) (6, 3) (7, 5) (8, 7) 
    (1, 4) (2, 6) (3, 1) (4, 5) (5, 2) (6, 8) (7, 3) (8, 7) 
    (1, 4) (2, 6) (3, 8) (4, 2) (5, 7) (6, 1) (7, 3) (8, 5) 
    (1, 4) (2, 6) (3, 8) (4, 3) (5, 1) (6, 7) (7, 5) (8, 2) 
    (1, 4) (2, 7) (3, 1) (4, 8) (5, 5) (6, 2) (7, 6) (8, 3) 
    (1, 4) (2, 7) (3, 3) (4, 8) (5, 2) (6, 5) (7, 1) (8, 6) 
    (1, 4) (2, 7) (3, 5) (4, 2) (5, 6) (6, 1) (7, 3) (8, 8) 
    (1, 4) (2, 7) (3, 5) (4, 3) (5, 1) (6, 6) (7, 8) (8, 2) 
    (1, 4) (2, 8) (3, 1) (4, 3) (5, 6) (6, 2) (7, 7) (8, 5) 
    (1, 4) (2, 8) (3, 1) (4, 5) (5, 7) (6, 2) (7, 6) (8, 3) 
    (1, 4) (2, 8) (3, 5) (4, 3) (5, 1) (6, 7) (7, 2) (8, 6) 
    (1, 5) (2, 1) (3, 4) (4, 6) (5, 8) (6, 2) (7, 7) (8, 3) 
    (1, 5) (2, 1) (3, 8) (4, 4) (5, 2) (6, 7) (7, 3) (8, 6) 
    (1, 5) (2, 1) (3, 8) (4, 6) (5, 3) (6, 7) (7, 2) (8, 4) 
    (1, 5) (2, 2) (3, 4) (4, 6) (5, 8) (6, 3) (7, 1) (8, 7) 
    (1, 5) (2, 2) (3, 4) (4, 7) (5, 3) (6, 8) (7, 6) (8, 1) 
    (1, 5) (2, 2) (3, 6) (4, 1) (5, 7) (6, 4) (7, 8) (8, 3) 
    (1, 5) (2, 2) (3, 8) (4, 1) (5, 4) (6, 7) (7, 3) (8, 6) 
    (1, 5) (2, 3) (3, 1) (4, 6) (5, 8) (6, 2) (7, 4) (8, 7) 
    (1, 5) (2, 3) (3, 1) (4, 7) (5, 2) (6, 8) (7, 6) (8, 4) 
    (1, 5) (2, 3) (3, 8) (4, 4) (5, 7) (6, 1) (7, 6) (8, 2) 
    (1, 5) (2, 7) (3, 1) (4, 3) (5, 8) (6, 6) (7, 4) (8, 2) 
    (1, 5) (2, 7) (3, 1) (4, 4) (5, 2) (6, 8) (7, 6) (8, 3) 
    (1, 5) (2, 7) (3, 2) (4, 4) (5, 8) (6, 1) (7, 3) (8, 6) 
    (1, 5) (2, 7) (3, 2) (4, 6) (5, 3) (6, 1) (7, 4) (8, 8)
    (1, 5) (2, 7) (3, 2) (4, 6) (5, 3) (6, 1) (7, 8) (8, 4) 
    (1, 5) (2, 7) (3, 4) (4, 1) (5, 3) (6, 8) (7, 6) (8, 2) 
    (1, 5) (2, 8) (3, 4) (4, 1) (5, 3) (6, 6) (7, 2) (8, 7) 
    (1, 5) (2, 8) (3, 4) (4, 1) (5, 7) (6, 2) (7, 6) (8, 3) 
    (1, 6) (2, 1) (3, 5) (4, 2) (5, 8) (6, 3) (7, 7) (8, 4) 
    (1, 6) (2, 2) (3, 7) (4, 1) (5, 3) (6, 5) (7, 8) (8, 4) 
    (1, 6) (2, 2) (3, 7) (4, 1) (5, 4) (6, 8) (7, 5) (8, 3) 
    (1, 6) (2, 3) (3, 1) (4, 7) (5, 5) (6, 8) (7, 2) (8, 4) 
    (1, 6) (2, 3) (3, 1) (4, 8) (5, 4) (6, 2) (7, 7) (8, 5) 
    (1, 6) (2, 3) (3, 1) (4, 8) (5, 5) (6, 2) (7, 4) (8, 7) 
    (1, 6) (2, 3) (3, 5) (4, 7) (5, 1) (6, 4) (7, 2) (8, 8) 
    (1, 6) (2, 3) (3, 5) (4, 8) (5, 1) (6, 4) (7, 2) (8, 7) 
    (1, 6) (2, 3) (3, 7) (4, 2) (5, 4) (6, 8) (7, 1) (8, 5) 
    (1, 6) (2, 3) (3, 7) (4, 2) (5, 8) (6, 5) (7, 1) (8, 4) 
    (1, 6) (2, 3) (3, 7) (4, 4) (5, 1) (6, 8) (7, 2) (8, 5) 
    (1, 6) (2, 4) (3, 1) (4, 5) (5, 8) (6, 2) (7, 7) (8, 3) 
    (1, 6) (2, 4) (3, 2) (4, 8) (5, 5) (6, 7) (7, 1) (8, 3) 
    (1, 6) (2, 4) (3, 7) (4, 1) (5, 3) (6, 5) (7, 2) (8, 8) 
    (1, 6) (2, 4) (3, 7) (4, 1) (5, 8) (6, 2) (7, 5) (8, 3) 
    (1, 6) (2, 8) (3, 2) (4, 4) (5, 1) (6, 7) (7, 5) (8, 3) 
    (1, 7) (2, 1) (3, 3) (4, 8) (5, 6) (6, 4) (7, 2) (8, 5) 
    (1, 7) (2, 2) (3, 4) (4, 1) (5, 8) (6, 5) (7, 3) (8, 6) 
    (1, 7) (2, 2) (3, 6) (4, 3) (5, 1) (6, 4) (7, 8) (8, 5) 
    (1, 7) (2, 3) (3, 1) (4, 6) (5, 8) (6, 5) (7, 2) (8, 4) 
    (1, 7) (2, 3) (3, 8) (4, 2) (5, 5) (6, 1) (7, 6) (8, 4) 
    (1, 7) (2, 4) (3, 2) (4, 5) (5, 8) (6, 1) (7, 3) (8, 6) 
    (1, 7) (2, 4) (3, 2) (4, 8) (5, 6) (6, 1) (7, 3) (8, 5) 
    (1, 7) (2, 5) (3, 3) (4, 1) (5, 6) (6, 8) (7, 2) (8, 4) 
    (1, 8) (2, 2) (3, 4) (4, 1) (5, 7) (6, 5) (7, 3) (8, 6) 
    (1, 8) (2, 2) (3, 5) (4, 3) (5, 1) (6, 7) (7, 4) (8, 6) 
    (1, 8) (2, 3) (3, 1) (4, 6) (5, 2) (6, 5) (7, 7) (8, 4) 
    (1, 8) (2, 4) (3, 1) (4, 3) (5, 6) (6, 2) (7, 7) (8, 5) 
    92

3.迷宫问题

迷宫问题描述：定义一个二维数组N\*M（其中2<=N<=10;2<=M<=10），如5 × 5数组下所示：

int maze[5][5] = {
    
        0, 1, 0, 0, 0,
    
        0, 1, 0, 1, 0,
    
        0, 0, 0, 0, 0,
    
        0, 1, 1, 1, 0,
    
        0, 0, 0, 1, 0,
    
    };

它表示一个迷宫，其中的1表示墙壁，0表示可以走的路，只能横着走或竖着走，不能斜着走，要求编程序找出从左上角到右下角的最短路线。入口点为\[0,0\],既第一空格是可以走的路。  
Input  
一个N × M的二维数组，表示一个迷宫。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道。  
Output  
左上角到右下角的最短路径，格式如样例所示。

**输入描述：**

输入两个整数，分别表示二位数组的行数，列数。再输入相应的数组，其中的1表示墙壁，0表示可以走的路。数据保证有唯一解,不考虑有多解的情况，即迷宫只有一条通道

**输出描述：**

左上角到右下角的最短路径，格式如样例所示。

**输入例子：**

5 5
    0 1 0 0 0
    0 1 0 1 0
    0 0 0 0 0
    0 1 1 1 0
    0 0 0 1 0

**输出例子：**

(0,0)
    (1,0)
    (2,0)
    (2,1)
    (2,2)
    (2,3)
    (2,4)
    (3,4)
    (4,4)

**解题思路：**  
采用回溯法来解决迷宫问题是非常有效的，可以走的位置标号为 0，是墙不能走的位置标号为 1，已经走过的位置标号为 2，当到达一个新位置时首先判断该位置是否有效位置（没有超出迷宫范围，不是墙，也没有走过），如果当前位置是有效位置就记录下当前位置，然后从东南西北四个方向依次考虑是否可以继续往前行走，如果四个方向都走不通那么就只能回溯。解空间是从出发点到结束位置的各个路径，状态节点是迷宫中各个位置，回溯时一定要注意将标记为已经走过的顶点恢复为没有走过，另外由于这道题是找最短路线，所以要注意用来记录最佳路径的bestPath要初始化为找到的第一条可行路径，否则bestPath初始路径长度为0，永远都找不到比它更短的路径。

代码：

#include <iostream>
    #include <vector>
    using namespace std;
    
    
    void walk_maze(int **maze, int n, int m, int a, int b, vector<pair<int, int> > &path, vector<pair<int, int> > &bestPath, bool &firstPath)
    {
        if(a < 0 || a >= n || b < 0 || b >= m || maze[a][b] != 0)
            return;
        if(a == (n-1) && b == (m-1))
        {
            path.push_back(make_pair(n-1, m-1));
            maze[a][b] = 2;
            if(firstPath)
            {
                for(vector<pair<int, int> >::iterator it = path.begin(); it != path.end(); ++it)
                {
                    bestPath.push_back(*it);
                }
                firstPath = false;
            }
            if(path.size() < bestPath.size())
            {
                bestPath.clear();
                for(vector<pair<int, int> >::iterator it = path.begin(); it != path.end(); ++it)
                {
                    bestPath.push_back(*it);
                }
            }
            path.pop_back();
            maze[a][b] = 0;
            return;
        }
        path.push_back(make_pair(a, b));
        maze[a][b] = 2;
        walk_maze(maze, n, m, a, b+1, path, bestPath, firstPath);
        walk_maze(maze, n, m, a+1, b, path, bestPath, firstPath);
        walk_maze(maze, n, m, a, b-1, path, bestPath, firstPath);
        walk_maze(maze, n, m, a-1, b, path, bestPath, firstPath);
        path.pop_back();
        maze[a][b] = 0;
    }
    void test1()
    {
        int n, m;
        while(cin >> n >> m)
        {
            int **maze = new int*[n];
            for(int i = 0; i < n; i++)
                maze[i] = new int[m];
            for(int i = 0; i < n; i++)
            {
                for(int j = 0; j < m; j++)
                {
                    cin >> maze[i][j];
                }
            }
            vector<pair<int, int> > path, bestPath;
            int a = 0, b = 0;
            bool firstPath = true;
            walk_maze(maze, n, m, a, b, path, bestPath, firstPath);
            for(vector<pair<int, int> >::iterator it = bestPath.begin(); it != bestPath.end(); ++it)
            {
                cout << "(" << it->first << "," << it->second << ")" << endl;
            }
    
            for(int i = 0; i < n; i++)
            {
                delete maze[i];
                maze[i] = 0;
            }
            delete [] maze;
            maze = 0;
        }
    }
    
    int main()
    {
        test1();
        return 0;
    }

[http_www.cnblogs.com_chinazhangjie_archive_2010_10_22_1858410.html]: http://www.cnblogs.com/chinazhangjie/archive/2010/10/22/1858410.html
[http_baike.baidu.com_link_url_m-I1xz9PSYf9Hr8koWBcx2JNnHVCmKT_wA4L4ryrqHocN-I6oTp-pnEl9HB3FhhT8Gr2J50mG-aNRmF6K5QHbnO3_GdQOFM7lxBvUUc0zfOnDVhjvNEToqqY8Xeng9zC]: http://baike.baidu.com/link?url=m-I1xz9PSYf9Hr8koWBcx2JNnHVCmKT_wA4L4ryrqHocN-I6oTp-pnEl9HB3FhhT8Gr2J50mG-aNRmF6K5QHbnO3_GdQOFM7lxBvUUc0zfOnDVhjvNEToqqY8Xeng9zC
[http_blog.csdn.net_na_beginning_article_details_62884939]: http://blog.csdn.net/na_beginning/article/details/62884939