第45课 递归的思想与应用（下）

#include <iostream>
#include "LinkList.h"

using namespace std;
using namespace DTLib;

struct Node
{
    int value;
    Node* next;
};

//创建无表头结点的单链表（己填充数据）：v结点的值，len链表长度
Node* create_list(int v, int len)
{
    Node* ret = NULL;
    Node* slider = NULL;

    for(int i=0; i<len; i++){
        Node* node = new Node();

        node->value = v++;
        node->next = NULL;

        //每创建好一个节点，slider指向这个节点
        if( slider == NULL ){
            slider = node;
            ret = node;
        }else{
            slider->next = node;
            slider = node;
        }
    }

    return ret;
}

void destroy_list(Node* list)
{
    while(list){
        Node* del = list;
        list = list->next;

        delete del;
    }
}

//打印链表的内容
void print_list(Node* list)
{
    while(list){
        cout << list->value << "->";
        list = list->next;
    }

    cout << "NULL" << endl;
}

//逆序打印单链表中的偶数结点
void r_print_even(Node* list)
{
    if(list != NULL){

        //深度搜索，直到最后一个节点
        r_print_even(list->next);

        //回溯算法设计：上一行递归结束，开始回溯并判断节点的值是否为偶数
        if(list->value % 2 == 0){
            cout << list->value << " ";
        }
    }
}

template<int N>
class QueenSolution : public Object
{
protected:

    struct Pos : public Object
    {
        int x;
        int y;
        Pos(int px = 0, int py = 0):x(px),y(py){}
    };

    int m_chessboard[N][N]; //棋盘: 原点0，0在左下角，x轴正方向向右，y轴正方向向上
    Pos m_direction[3];     //三个方向向量
    LinkList<Pos> m_solution;
    int m_count;

    void init()
    {
        m_count = 0;

        //初始化棋盘
        for(int i=0; i<N; i++){
            for (int j=0; j<N; j++){
                m_chessboard[i][j] = 0;
            }
        }

        //初始化方向矢量
        //左下角
        m_direction[0].x =-1;
        m_direction[0].y =-1;
        //向下
        m_direction[1].x =0;
        m_direction[1].y =-1;
        //右下角
        m_direction[2].x =1;
        m_direction[2].y =-1;
    }

    //打印棋盘内容
    void print()
    {
        typename LinkList<Pos>::iterator iter = m_solution.begin();

        while(iter != m_solution.end()){
            cout << "(" << (*iter).x <<"," <<(*iter).y <<") ";
            iter++;
        }

        cout << endl;

        for(int y=0; y<N; y++){
            for (int x=0; x<N; x++){
                switch (m_chessboard[x][y]) {
                    case 0:cout << " ."; break;
                    case 1:cout << " #"; break;
                }
            }
            cout << endl;
        }

        cout << endl;
    }

    bool isInner(int x, int y)
    {
        return (0<=x) && (x<N) && (0<=y) && (y<N);
    }

    //检测在棋盘的（x，y）位置是否可以放置皇后
    bool check(int x, int y, int d)
    {
        bool ret = true;

        while(ret && isInner(x, y))
        {
            ret = ret && (m_chessboard[x][y] == 0);
            x += m_direction[d].x;
            y += m_direction[d].y;
        }

        return ret;
    }

    //在第row行尝试放置皇后
    void place(int row)
    {
        int y = row;
        if(row < N){
            for(int x=0; x<N; x++){
                if(check(x, y, 0) && check(x, y, 1) && check(x, y, 2)){
                    m_chessboard[x][y] = 1; //放置皇后
                    m_solution.insert(Pos(x,y)); //将该位置加入链表

                    place(row + 1); //在下一行放置皇后。

                    //当place(row+1)函数返回时，表示第row+1行无法找到放置皇后的地方（或找到解决方案后正常返回）
                    m_chessboard[x][y] = 0; //回溯,将当前位置的皇后移除。
                    m_solution.remove(m_solution.length() - 1);
                }
            }
        }else{
            //由于采用深度优先搜索，所以放置到第SIZE行时，表示己经找到解决方案
            m_count++;  //每找到一行方案，m_count加1。
            print();    //打印解决方案
        }
    }

public:
    QueenSolution(){init();}

    void solve()
    {
        place(0); //从第0行开始放置
        cout << "total : " << m_count << endl;
    }

};

int main()
{
    //测试：逆序打印单链表中的偶数结点
    Node* list = create_list(1, 10);
    print_list(list);


    r_print_even(list);

    destroy_list(list);

    cout << endl;

    //测试：八皇后解决方案
    QueenSolution<8> qs;
    qs.solve();

    return 0;
}
/*测试结果：
1->2->3->4->5->6->7->8->9->10->NULL
10 8 6 4 2
(0,0) (4,1) (7,2) (5,3) (2,4) (6,5) (1,6) (3,7) //显示时，使用的坐标系（原点在左上角，x向右为正，y向下为正）
 # . . . . . . .
 . . . . # . . .
 . . . . . . . #
 . . . . . # . .
 . . # . . . . .
 . . . . . . # .
 . # . . . . . .
 . . . # . . . .

(0,0) (5,1) (7,2) (2,3) (6,4) (3,5) (1,6) (4,7)
 # . . . . . . .
 . . . . . # . .
 . . . . . . . #
 . . # . . . . .
 . . . . . . # .
 . . . # . . . .
 . # . . . . . .
 . . . . # . . .

 //省略其余解决方案...

total : 92
*/