#ifndef _WORD_SOLITAIRE_H_#define _WORD_SOLITAIRE_H_#include <list>#include <map>#include <queue>#include <iostream>#include <stdlib.h>#include <limits.h>using namespace std;/* *@struct structWord * *@brief 单词结构体 */typedef struct{    // 单词    string strWord;    // 搜索深度    int idepth;    // 是否访问过    bool bVisit;}structWord;// 单词map,key为24个字母，value为以字母开头的单词listtypedef map<char, list<structWord>> WORDMAP;/* *@class CWordManager * *@brief 单词管理类 */class CWordManager{public:    // 构造函数    CWordManager();    // 析构函数    ~CWordManager();public:    // 初始化    void InitialMap();    // 增加单词,成功返回true    bool AddWord(string strWord);    // 获取mapWord    WORDMAP GetMapWord();    // 单词是否存在，存在返回true    bool IsWordExist(string strWord);    // 找出已strStart最后一个字母开头的单词,没找到返回“0”    string Find_Letter_With_AStart(string strStart);    // 获取最少接龙包含的单词个数，不能形成接龙返回-1    int get_word_number_of_least_solitaire(string strHead, string strTail);    // A单词尾字母是否等于B单词首字母,等于返回true    bool Is_ATail_Equal_BHead(string strA, string strB);    // 找出以strA尾字母为开头字母的单词list    list<structWord> Find_List_With_ATail(string strA);    // 获取最短接龙的长度，不能形成接龙返回0    int get_length_of_shortest_solitaire(string strHead, string strTail);    // 深度优先搜索    void DepthFirstSearch(structWord& sStart, string strTail, int& iMinLen);    // 是否是终点，是返回true，并记录路径    bool IsEnd(string strEnd, string strTail, int& iMinLen);    // 单词是否在路径中出现过,出现过返回true    bool IsWordExistInListPath(list<string> listPath, string strWord);    // 返回list中string总长度    int CountListLenth(list<string> listWord);    void clear(void);private:    // 单词map,key为26个字母，value为以字母开头的单词list    WORDMAP mapWord;    // 单词list    list<structWord> listWord;    // 路径list,存储起点到终点的所有路径    list<list<string>> listAllPath;    // 路径list，存储起点到终点的一条路径    list<string> listPath;};int add_word(const char *word);int get_word_number_of_least_solitaire (const char *head, const char *tail);int get_length_of_shortest_solitaire (const char *head, const char *tail);void clear(void);#endif /* _WORD_SOLITAIRE_H_ */

#include "word_solitaire.h"CWordManager classWord;/**********************************************************功能：添加单词输入：单词输出：无返回：成功返回0, 其他返回-1（如：单词已经存在）**********************************************************/int add_word(const char *word){    string strWord = word;    // 添加单词    return classWord.AddWord(strWord)?0:-1;}/************************************************************************************************功能：获取最少接龙包含的单词个数输入：head 龙头      tail 龙尾输出：无返回：单词个数（如果不能形成接龙、指定龙头龙尾不存在、龙头龙尾相同等，返回-1）**************************************************************************************************/int get_word_number_of_least_solitaire(const char *head, const char *tail){    string strHead = head;    string strTail = tail;    int iResult = classWord.get_word_number_of_least_solitaire(strHead, strTail);    return (-1 == iResult)?-1:(iResult + 2);}/************************************************************************************************功能：获取最短接龙的长度输入：head 龙头      tail 龙尾输出：无返回：接龙的长度（如果不能形成接龙、指定龙头龙尾不存在、龙头龙尾相同等，返回-1）**************************************************************************************************/int get_length_of_shortest_solitaire (const char *head, const char *tail){    string strHead = head;    string strTail = tail;    int iResult = classWord.get_length_of_shortest_solitaire(strHead, strTail);    clear();    return (0 == iResult)?-1:iResult;}/*******************************************************************************************************************************功能：清空数据输入：无输出：无返回：无*********************************************************************************************************************************/void clear(void){    classWord.clear();    classWord.InitialMap();}// 构造函数CWordManager::CWordManager(){    InitialMap();}// 析构函数CWordManager::~CWordManager(){    mapWord.clear();}// 初始化void CWordManager::InitialMap(){    for (char chWord = ‘a‘; chWord <= ‘z‘; chWord++)    {        pair<WORDMAP::iterator, bool> PairWord = mapWord.insert(WORDMAP::value_type(chWord, listWord));        if (!PairWord.second)        {            // 插入失败            cout << "insert into mapWord failed!" << endl;        }    }}// 增加单词,成功返回truebool CWordManager::AddWord(string strWord){    // 单词已经存在    if (IsWordExist(strWord))    {        return false;    }    char chFirstLetter = strWord[0];    WORDMAP::iterator iter = mapWord.find(chFirstLetter);    structWord sWord;    sWord.strWord = strWord;    sWord.idepth = 0;    sWord.bVisit = false;    iter->second.push_back(sWord);    return true;}// 获取mapWordWORDMAP CWordManager::GetMapWord(){    return mapWord;}// 单词是否存在，存在返回truebool CWordManager::IsWordExist(string strWord){    char chFirstLetter = strWord[0];    WORDMAP::iterator iter = mapWord.find(chFirstLetter);    list<structWord> listWord = iter->second;    for (list<structWord>::iterator it = listWord.begin(); it != listWord.end(); it++)    {        if (!strcmp(strWord.c_str(), (*it).strWord.c_str()))        {            return true;        }    }    return false;}// 找出已strStart最后一个字母开头的单词,没找到返回“0”string CWordManager::Find_Letter_With_AStart(string strStart){    return "0";}void CWordManager::clear(void){    mapWord.clear();    listWord.clear();    listPath.clear();    listAllPath.clear();}//获取最少接龙包含的单词个数，不能形成接龙返回-1int CWordManager::get_word_number_of_least_solitaire(string strHead, string strTail){    if (!IsWordExist(strHead)         || !IsWordExist(strTail)         || !strcmp(strHead.c_str(), strTail.c_str()))    {        // 指定龙头龙尾不存在、龙头龙尾相同        return -1;    }    string strReverseWord(strHead);    reverse(strReverseWord.begin(), strReverseWord.end());    if (strReverseWord[0] == strTail[0])    {        // 直接可以接龙        return 0;    }    // 单词队列    queue<structWord> queWord;    structWord sWord;    sWord.strWord = strHead;    sWord.idepth = 0;    sWord.bVisit = true;    // 第一个单词入队列    queWord.push(sWord);    // 宽度优先搜索    while (!queWord.empty())    {        // 第一个元素出队列        structWord sNextWord = queWord.front();        queWord.pop();        // 找出以strWord尾字母为开头字母的单词list        list<structWord> listWord = Find_List_With_ATail(sNextWord.strWord);        for (list<structWord>::iterator it = listWord.begin(); it != listWord.end(); it++)        {            // 接龙完成            if (Is_ATail_Equal_BHead((*it).strWord, strTail))            {                it->idepth = sNextWord.idepth;                return (++(*it).idepth);            }            // 如果单词未曾遍历则入队列            if (!(it->bVisit))            {                it->bVisit = true;                // 搜索深度+1                it->idepth = sNextWord.idepth + 1;                queWord.push(*it);            }        }    }    // 不能形成接龙    return -1;}// 找出以strA尾字母为开头字母的单词listlist<structWord> CWordManager::Find_List_With_ATail(string strA){    string strReverseWord(strA);    reverse(strReverseWord.begin(), strReverseWord.end());    WORDMAP::iterator& it = mapWord.find(strReverseWord[0]);    return it->second;}// A单词尾字母是否等于B单词首字母,等于返回truebool CWordManager::Is_ATail_Equal_BHead(string strA, string strB){    string strAReverse(strA);    reverse(strAReverse.begin(), strAReverse.end());    return (strAReverse.at(0) == strB.at(0))?true:false;}// 获取最短接龙的长度，不能形成接龙返回0int CWordManager::get_length_of_shortest_solitaire(string strHead, string strTail){    if (!IsWordExist(strHead)         || !IsWordExist(strTail)         || !strcmp(strHead.c_str(), strTail.c_str()))    {        // 指定龙头龙尾不存在、龙头龙尾相同        return 0;    }    string strReverseWord(strHead);    reverse(strReverseWord.begin(), strReverseWord.end());    if (strReverseWord[0] == strTail[0])    {        // 直接可以接龙        return (int)(strHead.size() + strTail.size());    }    WORDMAP::iterator& iter = mapWord.find(strHead[0]);    list<structWord>& listWord = iter->second;    for (list<structWord>::iterator it = listWord.begin(); it != listWord.end(); it++)    {        if (!strcmp((it->strWord).c_str(), strHead.c_str()))        {            it->bVisit = true;            int iMinLen = INT_MAX;            DepthFirstSearch(*it, strTail, iMinLen);            break;        }    }    if (listAllPath.empty())    {        return 0;    }    int iMin = INT_MAX;    for (list<list<string>>::iterator it = listAllPath.begin(); it != listAllPath.end(); it++)    {        int iLen = 0;        for (list<string>::iterator iter = it->begin(); iter != it->end(); iter++)        {            iLen += (int)iter->size();        }        if (iMin > iLen)        {            iMin = iLen;        }    }    return iMin;}// 深度优先搜索void CWordManager::DepthFirstSearch(structWord& sStart, string strTail, int& iMinLen){    // 已访问过    sStart.bVisit = true;    // 路径入队列    listPath.push_back(sStart.strWord);    // 当前路径已经比最短路径长结束本次搜索    if (CountListLenth(listPath) > iMinLen)    {        listPath.pop_back();        return;    }    // 找出以strWord尾字母为开头字母的单词list    list<structWord> listWord = Find_List_With_ATail(sStart.strWord);    for (list<structWord>::iterator it = listWord.begin(); it != listWord.end(); it++)    {        // 已经出现过一次的单词不能再出现        if (this->IsWordExistInListPath(listPath, it->strWord))        {            continue;        }        // 如果没有遍历过并且不是终点        if (!(it->bVisit) && !(IsEnd(it->strWord, strTail, iMinLen)))        {            DepthFirstSearch(*it, strTail, iMinLen);        }    }    listPath.pop_back();}// 是否是终点，是返回true，并记录路径bool CWordManager::IsEnd(string strEnd, string strTail, int& iMinLen){    if (!strcmp(strTail.c_str(), strEnd.c_str()))    {        listPath.push_back(strTail);        listAllPath.push_back(listPath);        listPath.pop_back();        int iMinLenTemp = 0;        for (list<string>::iterator it = listPath.begin(); it != listPath.end(); it++)        {            iMinLenTemp += (int)it->size();        }        if (iMinLenTemp < iMinLen)        {            iMinLen = iMinLenTemp;        }        return true;    }    return false;}// 单词是否在路径中出现过bool CWordManager::IsWordExistInListPath(list<string> listPath, string strWord){    for (list<string>::iterator it = listPath.begin(); it != listPath.end(); it++)    {        if (!strcmp((*it).c_str(), strWord.c_str()))        {            return true;        }    }    return false;}// 返回list中string总长度int CWordManager::CountListLenth(list<string> listWord){    int iLen = 0;    for (list<string>::iterator it = listWord.begin(); it != listWord.end(); it++)    {        iLen += (int)it->size();    }    return iLen;}