多叉树的迷宫

年轻人的第一棵多叉树

既然是多叉树那么解迷宫的功能自然比queue要多要快
求单源最短路次短路输出所有最短次短任意次短路径不在话下
不过敲得冗余真的好吗
//其实还是有BUG的

//wulian162 1619500007 lpy 
//2017.3.26-2.17.3.28
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int INF = 100000;
const int M = 8, N = 6;
struct TreeNode{

    char _direct;// l d r u  
    pair<int, int> _coordinate;
    int _index;//index of this->father->children (sib)
    int _depth;
    TreeNode *father;
    vector<TreeNode*> children;//number of children <= 4 (l u r d)
//    TreeNode *sibling; //sibling can be defined by other children members of father  thus it is unnecessary to set the member 
    TreeNode *cousin;//if _index != lastChildNum ,points to Null,otherwise points to true next(nearby) cousin 

    TreeNode(char d):_direct(d), _coordinate(make_pair(0, 0)), father(NULL), cousin(NULL){_depth = depthCounter(); _index = indexCounter();}
    TreeNode(char d,TreeNode *f):_direct(d), father(f), cousin(NULL){father->children.push_back(this); _depth = depthCounter(); _index = indexCounter(); _coordinate = coordinateCounter();}

    int depthCounter();
    int indexCounter();
    pair<int, int> coordinateCounter();
    int getDepth();
    int insertAsChild(TreeNode *childNode);
    bool hasSibling();
    bool hasNextSibling();
    bool hasPrevSibling();
    TreeNode* getFirstSibling();
    TreeNode* nextSibling();
    TreeNode* prevSibling();
};


struct Tree{
    TreeNode *root;
    int _height;

    Tree():root(NULL), _height(0) {}

    bool insertAsRoot(TreeNode *node, pair<int, int> S);
    int updateHeight();
    int getHeight();
    TreeNode* getRoot();
    TreeNode* creatNode(char dir);
    TreeNode* creatNode(char dir, TreeNode *f);
};

int findE(pair<int, int> S);
void showPath(TreeNode *leaf, Tree &tree);
int dirToNumY(char dir);
int dirToNumX(char dir);
///////////////////////////////////////////////////
///////////////////////////////////////
/////////////////////input area1 start 
/////////////////////////
char maze[M + 1][N + 1] = {
    //ok
    
    '.',  '.','.','.','.','.','.',

    '.',  '.','.','#','.','.','.',
    '.',  '#','E','#','.','.','.',
    '.',  '#','S','E','#','.','.',
    '.',  'E','#','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.'

    //ok
    /*
    '.',  '.','.','.','.','.','.',

    '.',  '.','.','#','.','.','.',
    '.',  '#','.','#','.','.','.',
    '.',  '#','S','.','#','.','.',
    '.',  'E','#','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.'
    */

    //bug1 cant show the second shortest path to E
    /*
    '.',  '.','.','.','.','.','.',

    '.',  '.','.','#','.','.','.',
    '.',  '.','.','#','.','.','.',
    '.',  '#','S','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','#','#','.','.','.',
    '.',  '.','.','E','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.'
    */
    //bug2 when E near the barrier  CRACK
    /*
    '.',  '.','.','.','.','.','.',

    '.',  '.','.','E','.','.','.',
    '.',  '.','.','#','.','.','.',
    '.',  '#','S','.','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','#','#','.','.','.',
    '.',  '#','.','#','.','.','.',
    '.',  '.','.','.','.','.','.',
    '.',  '.','.','.','.','.','.'
    */

};
///////////////////////////////////////////////////
///////////////////////////////////////
/////////////////////input area1 end 
/////////////////////////
bool used[M + 1][N + 1];//[9][7]
pair<int, int> S, E;//coordinate of S E (y,x)
vector<TreeNode*> ePointer;//pointers point to E leaf(leaves)

bool needNewEntrance = true;//close if you jump and open if you have no next relation
queue<TreeNode*> toCousin;
TreeNode *entrance;//jump to entrance if have no sibl or cous(next)
Tree tree;


int main(){
    /*for(int i = 1;i <= M;i++)
    for(int j = 1;j <= N;j++){
    maze[i][j] = getchar();
    used[i][j] = false;
    if(maze[i][j] == 'S'){
    S = make_pair(i,j);
    used[i][j] = true;
    }
    else if(maze[i][j] == 'E')
    E = make_pair(i,j);

    }//draw the maze and mark the S/E
    */
    ///////////////////////////////////////////////////
    ///////////////////////////////////////
    /////////////////////input area2 start
    /////////////////////////
    S = make_pair(3, 2);
    used[S.first][S.second] = true;

    ///////////////////////////////////////////////////
    ///////////////////////////////////////
    /////////////////////input area2 start
    /////////////////////////
    int ans;//the shortest path
    //    for(int i = 1;i <= M;i++)
    //        for(int j = 1;j <= N;j++){
    //            if(maze[i][j] == 'S')
    //                ans = findE(i,j);
    ans = findE(S);
    cout << ans << endl;
    for (int i = 0;i < ePointer.size();i++){
        showPath(ePointer[i], tree);
        cout << endl;
    }
    return 0;
}
int findE(pair<int, int> S){
    TreeNode *mRoot = new TreeNode('0');//'0'means start. num = 0,depth = 0
    TreeNode *current = mRoot;//fix/////////////////////////////////////////////////////
    if(!tree.insertAsRoot(mRoot, S))
        return -1;
    int dy[4] = { 0,1,0,-1};//direction:
    int dx[4] = {-1,0,1, 0};//left down right up
    static bool foundDepthOfE = false;
    static int  depthOfE;
    TreeNode *itera;
    //while(1){
    //for(TreeNode *it = ((current != tree.root) ? current->father->children.front() : current);it != ((current != tree.root) ? current->father->children.back():  /***********/ );ite++){// root->father = NULL
    do{
        for(int ii = 0;ii < 4;ii++){
            if(
                current->_coordinate.first + dy[ii] > M ||
                current->_coordinate.first + dy[ii] < 1 ||
                current->_coordinate.second + dx[ii] > N ||
                current->_coordinate.second + dx[ii] < 1 ||
                used[current->_coordinate.first + dy[ii]][current->_coordinate.second + dx[ii]] ||
                maze[current->_coordinate.first + dy[ii]][current->_coordinate.second + dx[ii]] == '#')

                continue;
            //else...
            used[current->_coordinate.first + dy[ii]][current->_coordinate.second + dx[ii]] = true;//注意 x y 更新

            switch(ii){
            case 0://left
                itera = tree.creatNode('l');
                current->insertAsChild(itera);
                break;
            case 1://down
                itera = tree.creatNode('d');
                current->insertAsChild(itera);
                break;
            case 2://right
                itera = tree.creatNode('r');
                current->insertAsChild(itera);
                break;
            case 3://up
                itera = tree.creatNode('u');
                current->insertAsChild(itera);
                break;
            default:
                break;
            }

            if (itera->_index == 0 && needNewEntrance == true && itera->_depth == current->_depth + 1 && itera->father == current){//in case of have no child thus itera->father is not equal to curren(true father)
                entrance = itera;
                needNewEntrance = false;
            }
            if(itera->_index == 0 && itera != entrance && !toCousin.empty() && itera->_depth == current->_depth + 1 && itera->father == current){

                itera->cousin = toCousin.front();
                toCousin.pop();
            }
            if(maze[current->_coordinate.first + dy[ii]][current->_coordinate.second + dx[ii]] == 'E'){
                ePointer.push_back(itera);// mark the E position in tree
                maze[current->_coordinate.first + dy[ii]][current->_coordinate.second + dx[ii]] = false;//E can be found repeatedly
                foundDepthOfE = true;
                depthOfE = itera->getDepth();
            }
        }//end for(...)


        if(current->children.size() > 0 && current != tree.root){ // the last of childen can point to the next cousin
            toCousin.push(current->children.back());
        }

        //       if(/*itera->_depth == current->_depth+1 && */itera->father = current && itera == current->children.back())
        // from = itera;//if cur have children

        if(current->hasNextSibling()){//root has no sib
            current = current->nextSibling();
            continue;
        }
        //else  no next sibling
        //then find current's cousin (not itera)
        if(current->cousin != NULL){
            current = current->cousin;//jump to cousin
            continue;
        }
        //else no sibling or cousin
        //then turn(down) to entrance
        if(entrance != NULL){
            current = entrance;
            entrance = NULL;
            needNewEntrance = true;
            continue;
        }
        //else current == root
        current = current->children[0];




        // if(itera->_index == current->children.size()-1){ //iteraHasNextCousin?
        //     itera->cousin = from;
        // }

        ////junmp to next cousin[0](if exists && cousin!=NULL)
        //        if(!cousin.empty() && itera->_index == current->children.size()-1){
        //            if(cousin.top() == NULL){//meet end of this depth
        // cousin.clear();  //doesnt have queue::clear()
        //               cousin.pop();
        // iii = -1 ;  //no member in it
        //               itera = entrance;//jump to cousin
        //            }
        //            itera = cousin.pop();
        // iii++;
        //            continue;//jump
        //        }
        tree.updateHeight();
        //current = (current->getFirstSibling())->children.front();//the first child ///////////BBBUUUGGG///////////////////////cant find uncle or cousin
    }while(!foundDepthOfE);///////////////////
    return depthOfE;
}

void showPath(TreeNode *leaf, Tree &tree){
    if(leaf != tree.root)
        showPath(leaf->father, tree);
    cout << leaf->_direct << " ";
}

int TreeNode::depthCounter(){
    //   if(father!=NULL && father->_depth == dC)//if any node add a child in current depth
    //      dC++;//dc has already updated.it wont repeatedly update in previous-current depth
    //   return dC;
    if(father == NULL)
        return 0;
    return father->_depth+1;
}
int TreeNode::indexCounter(){
    if (father == NULL)
        return 0;
    return father->children.size()-1;
}
pair<int, int> TreeNode::coordinateCounter(){
    if(_coordinate.first != 0 && _coordinate.second != 0) {//root that has coor
        return _coordinate; //return themselves
    }
    else if(father == NULL)
        return make_pair(0, 0);
    else {//has father
        char myDir = _direct;
        pair<int, int> fatherCopr = father->_coordinate;
        switch(myDir){
        case 'l':
            _coordinate = make_pair(fatherCopr.first, fatherCopr.second - 1);
            break;
        case 'd':
            _coordinate = make_pair(fatherCopr.first + 1, fatherCopr.second);
            break;
        case 'r':
            _coordinate = make_pair(fatherCopr.first, fatherCopr.second + 1);
            break;
        case 'u':
            _coordinate = make_pair(fatherCopr.first - 1, fatherCopr.second);
            break;
        case '0'://impossible
            _coordinate = make_pair(fatherCopr.first, fatherCopr.second);
        default:
            break;

        }
    }
    return _coordinate;

}
int TreeNode::getDepth(){
    return _depth;
}
int TreeNode::insertAsChild(TreeNode *childNode){//O(1)
    children.push_back(childNode); //father-->child
    childNode->father = this;//child-->father
    childNode->_index = childNode->indexCounter();//update index automatically
    childNode->_depth = childNode->depthCounter();//update depth automatically
    childNode->_coordinate = childNode->coordinateCounter();
    return children.size();//the number of child added
}
//    int insertAsSibling(TreeNode *brotherNode){
//        
//    }
bool TreeNode::hasSibling(){//O(1)
    if(_depth == 0)//root has no father
        return false;
    return father->children.size() > 1 ? true : false;//size == 1 means that father only has this as his child
}
bool TreeNode::hasNextSibling(){//O(1)
    if(_depth == 0)//root
        return false;
    return (_index < father->children.size()-1) ? true : false;
}
bool TreeNode::hasPrevSibling(){//O(1)
    return _index > 0 ? true : false;
}
TreeNode* TreeNode::getFirstSibling(){//O(1)
    if(!hasSibling() && _depth != 0)
        return NULL;
    if(_depth == 0)//has no father
        return this;
    if(_index > 0)
        return father->children[0];
    return father->children[1];
}
TreeNode* TreeNode::nextSibling(){//O(1)
    if (!hasSibling())
        return NULL;
    if (!hasNextSibling())//not true sib
        return this;
    return father->children[_index + 1];
}
TreeNode* TreeNode::prevSibling(){//O(1)
    if (!hasSibling())
        return NULL;
    if (!hasPrevSibling())
        return this;
    return father->children[_index - 1];
}

bool Tree::insertAsRoot(TreeNode *node, pair<int, int> S){//O(1)
    root = node;
    node->_coordinate = S;
    return root ? true : false;
}
int Tree::updateHeight() {
    return ++_height;
}
int Tree::getHeight(){
    return _height;
}
TreeNode* Tree::getRoot(){
    return root;
}
TreeNode* Tree::creatNode(char dir){//do not have father
    TreeNode *node = new TreeNode(dir);
    return node;
}
TreeNode* Tree::creatNode(char dir, TreeNode *f){//has father
    TreeNode *node = new TreeNode(dir, f);
    return node;
}










/*
char maze[M + 1][N + 1] = {
'.','.','.','.','.','.','.',
'.','.','.','.','.','.','.',
'.','.','.','.','.','.','.',
'.','#','S','.','.','.','.',
'.','.','.','.','.','.','.',
'.','.','#','#','.','.','.',
'.','.','.','E','.','.','.',
'.','.','.','.','.','.','.',
'.','.','.','.','.','.','.'
};
*/

标签: none

添加新评论