#pragma once#include <stdio.h>#include <stdlib.h>#include <iostream>#include <vector>#include <list>#include <map>#include <algorithm>using namespace std;typedef map<int, int> DUSHUMAP;//结构体tLine表示一条双向的线段typedef struct{    int pot1;    int pot2;}tLine;//一笔画出给定图形int OneLineDrawMap (int n, tLine *arrLines, int* aDrawline) ;// 构造度数mapbool BuildMap(int n, tLine* arrLines, DUSHUMAP& mapDuShu);// 是否存在欧拉回路，存在返回truebool IsExistOulaHuiLu(int iJiDian, DUSHUMAP mapDuShu);// 深度优先搜索求解void DepthFirstSearch(int iStartpoint, int n, DUSHUMAP& mapDuShu, list<int>& listPath, vector<tLine>& vecLine);// 判断两点之间存不存在边，存在返回truebool IsLineBetween2Point(int iPointA, int iPointB, vector<tLine> vecLine);void search(int x,int *ans,int **a,int *d,int &m,int n);

#include "CellularDistrict.h"/************************************************************************Description  : 一笔画出给定图形Prototype    :  Input Param  : n表示要画的线段的条数                arrLines表示由多条线段组成的图形，由调用者负责指针的分配，释放和保证合法性Output Param :     aDrawline输出画线顺序，调用者保证指针合法性，由调用者负责指针的分配，释放和保证合法性Return Value :     成功返回 0 ，失败返回-1/************************************************************************/int OneLineDrawMap (int n, tLine* arrLines, int* aDrawline) {    // 构造度数map,key为节点序号，value为该序号的度数    DUSHUMAP mapDuShu;    if (!BuildMap(n, arrLines, mapDuShu))    {        cout << "insert into mapDuShu failed!" << endl;        return -1;    }    // 奇点个数    int iJiDian = 0;    // 判断是否能一笔画    if (!IsExistOulaHuiLu(iJiDian, mapDuShu))    {        return -1;    }    // 选定一个点为起点,欧拉定理，如果有2个点度为奇数，则只能选其中一个作为起点，另一个为终点    int iStartpoint = 1;    if (2 == iJiDian)    {        for (DUSHUMAP::iterator it = mapDuShu.begin(); it != mapDuShu.end(); it++)        {            if (1 == (it->second) % 2)            {                iStartpoint = it->first;                break;            }        }    }    // 边vector    vector<tLine> vecLine;    for (int i = 0; i < n; i++)    {        vecLine.push_back(arrLines[i]);    }    // 路径list    list<int> listPath;    // 深度优先搜索，递归求解路径    DepthFirstSearch(iStartpoint, n, mapDuShu, listPath, vecLine);    // 反序输出    reverse(listPath.begin(), listPath.end());    for (list<int>::iterator it = listPath.begin(); it != listPath.end(); it++)    {        *aDrawline = *it;        aDrawline++;    }    return 0;}// 构造度数mapbool BuildMap(int n, tLine* arrLines, DUSHUMAP& mapDuShu){    for (int i = 1; i <= n; i++)    {        std::pair<map<int, int>::iterator, bool> PairRev = mapDuShu.insert(map<int, int>::value_type(i, 0));        if (!PairRev.second)        {            return false;        }    }    for (int i = 1; i <= n; i++)    {        int iPort1 = arrLines[i - 1].pot1;        int iPort2 = arrLines[i - 1].pot2;        for (DUSHUMAP::iterator it = mapDuShu.begin(); it != mapDuShu.end(); it++)        {            if ((it->first == iPort1) || (it->first == iPort2))            {                (it->second)++;            }        }    }    // 删除多余的key    DUSHUMAP mapTemp(mapDuShu);    for (DUSHUMAP::iterator it = mapDuShu.begin(); it != mapDuShu.end(); it++)    {        if (0 == it->second)        {            DUSHUMAP::iterator iter = mapTemp.find(it->first);            mapTemp.erase(iter);        }    }    mapDuShu = mapTemp;    return true;}// 是否存在欧拉回路bool IsExistOulaHuiLu(int iJiDian, DUSHUMAP mapDuShu){    for (DUSHUMAP::iterator it = mapDuShu.begin(); it != mapDuShu.end(); it++)    {        if (1 == (it->second) % 2)        {            iJiDian++;        }    }    // 欧拉定理，无向图存在欧拉路的充要条件是恰有0或2个点度为奇数    if ((1 == iJiDian) || (iJiDian > 2))    {        return false;    }    return true;}// 深度优先搜索求解void DepthFirstSearch(int iStartpoint, int n, DUSHUMAP& mapDuShu, list<int>& listPath, vector<tLine>& vecLine){    DUSHUMAP::iterator itValue = mapDuShu.find(iStartpoint);    if (0 == itValue->second)    {        // 当前节点度数为0，加入输出队列        listPath.push_back(iStartpoint);        return;    }    for (int i = 1; i <= (int)mapDuShu.size(); i++)    {        if (IsLineBetween2Point(iStartpoint, i, vecLine))        {            // 已经遍历过的边删掉            vector<tLine>::iterator it = vecLine.begin();            for (; it != vecLine.end(); it++)            {                if (((iStartpoint == it->pot1) && (i == it->pot2))                    || ((i == it->pot1) && (iStartpoint == it->pot2)))                {                    break;                }            }            vecLine.erase(it);            // 已经遍历过的节点度数减1            (itValue->second)--;            itValue = mapDuShu.find(i);            (itValue->second)--;            // 递归搜索            DepthFirstSearch(i, n, mapDuShu, listPath, vecLine);        }    }    // 起点最后入队列    listPath.push_back(iStartpoint);}// 判断两点之间存不存在边，存在返回truebool IsLineBetween2Point(int iPointA, int iPointB, vector<tLine> vecLine){    for (vector<tLine>::iterator it = vecLine.begin(); it != vecLine.end(); it++)    {        if (((iPointA == it->pot1) && (iPointB == it->pot2))            || ((iPointB == it->pot1) && (iPointA == it->pot2)))        {            return true;        }    }    return false;}