迷宫问题的代码看不懂了,求大佬注释

为啥要这么定义pos?都没怎么看懂,,,和普通01迷宫有点差别,,生成全联通迷宫找最短路径,,求大佬注释55

#include "pch.h"// pch.cpp: 与预编译标头对应的源文件;编译成功所必需的

#define INT_N 999
#define MAX_DIS 2147483647
using namespace std;//using声明,使程序可以使用程序包含的任何标准C++头文件中的所有名字


Node::Node()
{


}


Node::~Node()//析构函数
{
}



int Graph::findEdge(int node)//找所有节点边的位置
{
    int pos = node / N * (N - 1) + node % N;//定义一个节点的行值
    int e = 0;
    if (node%N == 0)//无左邻居 
    { 
        if (row[pos])
            e |= Right;//就向右插边
    }
    else if (node%N == N - 1)//无右邻
    {
        if (row[pos - 1])
            e |= Left;//就向左插边
    }
    else
    {
        if (row[pos])
            e |= Right;
        if (row[pos - 1]) 
            e |= Left;
    }

    int p2 = (node%N)*(N - 1) + node / N;//定义节点的列值
    if (node < N) {
        //无上邻居
        if (col[p2])
            e |= Down;//可以向下插边
    }
    else if (node >= N * (N - 1)) {
        //无下邻
        if (col[p2 - 1])
            e |= Up;//可以向上插边
    }
    else {
        if (col[p2])
            e |= Down;
        if (col[p2 - 1]) 
            e |= Up;
    }
    return e;//返回节点的边,存在e里,得到所有边的位置
}

void Graph::make_rand(int * a)
{

    int p = rand() % 4;
    int q = rand() % 4;
    if (p != q) 
    {
        int n = a[p];
        a[p] = a[q];
        a[q] = n;
    }
}

int Graph::findNode(int node, int Direction)
{
    if (Direction & Left) 
    {
        if (node%N != 0) return node - 1;
        else return -1;
    }
    else if (Direction & Right)
    {
        if (node%N == N - 1) return -1;
        else return node + 1;
    }
    else if (Direction &Up)
    {
        node = node - N;
        if (node < 0) return -1;
        return node;
    }
    else if (Direction & Down) 
    {
        node = node + N;
        if (node > N*N - 1) return -1;
        return node;
    }
    return -1;
}

int Graph::findNode2(int node, int Direction)
{
    int pos = node / N * (N - 1) + node % N;
    int pos2 = (node%N)*(N - 1) + node / N;
    if (Direction & Left) {
        if (node%N != 0 && row[pos - 1]) return node - 1;
        else return -1;
    }
    else if (Direction & Right) {
        if (node%N != (N - 1) && row[pos]) return node + 1;
        else return -1;
    }
    else if (Direction &Up) {
        node = node - N;
        if (node >= 0 && col[pos2 - 1]) return node;
        return -1;
    }
    else if (Direction & Down) {
        node = node + N;
        if (node > N*N - 1) return -1;
        if (col[pos2]) return node;
        return -1;
    }
    return -1;
}

void Graph::addEdge(int node, int Direction)
{
    if (Direction & Left || Direction & Right) {
        //左右方向--
        int pos = node / N * (N - 1) + node % N;
        if ((Direction & Left) && node%N != 0) row[pos - 1] = true;
        if ((Direction & Right) && node%N != N - 1) row[pos] = true;
    }
    if (Direction & Up || Direction & Down) {
        //上下方向--
        int p2 = (node%N)*(N - 1) + node / N;
        if ((Direction & Down) && node < N*(N - 1)) col[p2] = true;
        if ((Direction &Up) && node > (N - 1)) col[p2 - 1] = true;
    }
}

void Graph::insertEdge(int from)
{
    //从from起 插入条边
    bool add = false;
    for (int start = from; start < 2 * N*(N - 1); start++) {
        int pos = 0;
        int r = start / (2 * N - 1);
        int c = start % (2 * N - 1);
        if (c > N - 1) {
            //列
            pos = (c - (N - 1))*(N - 1) + r;
            if (col[pos] == false) {
                col[pos] = true;
                //add = true;
                return;
            }
        }
        else {
            //行
            pos = r * (N - 1) + c;
            if (row[pos] == false) {
                row[pos] = true;
                return;
            }
        }
    }

    for (int start = from; start >= 0; start--) {
        int pos = 0;
        int r = start / (2 * N - 1);
        int c = start % (2 * N - 1);
        if (c > N - 1) {
            //列
            pos = (c - (N - 1))*(N - 1) + r;
            if (col[pos] == false) {
                col[pos] = true;
                //add = true;
                return;
            }
        }
        else {
            //行
            pos = r * (N - 1) + c;
            if (row[pos] == false) {
                row[pos] = true;
                return;
            }
        }
    }
}

void Graph::test(int node)
{

    int e = findEdge(node);
    printf("node=%d,Up=%d,Down=%d,Left=%d,Right=%d", node, e&Up, e&Down, e&Left, e&Right);


}

Graph::Graph(int n)
{
    N = n;
    if (N < 2) N = 2;
    row = new bool[N*(N - 1)];
    col = new bool[N*(N - 1)];
}

Graph::~Graph()
{
    delete col;
    delete row;
}


bool Graph::travel(int start, vector<int> & visit, bool * have)
{
    int count = N * N;
    int order[4] = { Left,Right,Up,Down };
    int c = 0;
    int node2 = 0;
    while (visit.size() < count) {
        if (c == 0) { c = 1; }
        else start = visit.back();
        //随机找一个方向开始--
        make_rand(order);
        bool insert = false;
        for (int j = 0; j < 4; j++) {
            node2 = findNode(start, order[j]);
            if (node2 >= 0 && have[node2] == false) {
                visit.push_back(node2);
                have[node2] = true;
                addEdge(start, order[j]);//添加这个方向的边
                insert = true;
                break;
            }
        }
        if (insert == false) return false;
    }
    return true;
}

void Graph::create()
{
    srand((unsigned)time(NULL));

    int total = N * N;
    bool * have = new bool[total];

    int i = 0;
    for (i = 0; i < total; i++) have[i] = false;

    for (i = 0; i < N*(N - 1); i++) {
        row[i] = false; col[i] = false;
    }
    vector<int> visit;//已访问的节点表
    vector<int> starts;//起点表

    int start = rand() % total;
    visit.insert(visit.end(), start);
    have[start] = true;
    starts.push_back(start);

    bool ok = travel(start, visit, have);
    while (ok == false) {
        start = visit[rand() % visit.size()];
        int nRet = std::count(starts.begin(), starts.end(), start);
        if (nRet > 0) {
            for (int j = 0; j < visit.size(); j++) {
                start = visit[j];
                nRet = std::count(starts.begin(), starts.end(), start);
                if (nRet == 0) break;
            }
        }
        ok = travel(start, visit, have);
        starts.push_back(start);
    }

    //随机 添加一部分边--
    int max = 2 * N * (N - 1);
    int min = N * N - 1;
    int need = (max + min) / 2;
    for (int k = min; k <= need; k++) {
        //--暂时留空--
        int edge = rand() % max;//随机增加的边
        //随机找一个起点,增加一个边
        insertEdge(edge);
    }

    delete have;
}

void Graph::print() {
    int i, pos, pos2;
    char buf[300];
    char buf2[300];
    char buf3[10];
    int max = N * N - 1;
    sprintf_s(buf3, "%d", max);
    int len = strlen(buf3);
    memset(buf3, 0, 10);
    for (i = 0; i < N*N; i++) {
        if (i%N == 0) {
            if (i > 0) {
                printf("%s\n", buf);
                printf("%s\n", buf2);
            }
            memset(buf, 0, 300);
            memset(buf2, 0, 300);
            memset(buf3, 0, 10);
        }
        if (len == 1) sprintf_s(buf3, "%d", i);
        else if (len == 2) sprintf_s(buf3, "%02d", i);
        else if (len == 3) sprintf_s(buf3, "%03d", i);
        else if (len == 4) sprintf_s(buf3, "%04d", i);
        else {
            printf("too big");
            return;
        }
        strcat_s(buf, buf3);
        pos = i / N * (N - 1) + i % N;//(N-1);
        if (i%N != (N - 1)) {
            if (row[pos]) strcat_s(buf, "-");
            else strcat_s(buf, " ");
        }

        pos2 = (i%N)*(N - 1) + i / N;
        if (i < N*(N - 1)) {
            if (col[pos2]) {
                if (len == 1) strcat_s(buf2, "| ");
                else if (len == 2) strcat_s(buf2, " | ");
                else if (len == 3) strcat_s(buf2, " |  ");
                else if (len == 4) strcat_s(buf2, "  |  ");
            }
            else {
                if (len == 1) strcat_s(buf2, "  ");
                else if (len == 2) strcat_s(buf2, "   ");
                else if (len == 3) strcat_s(buf2, "    ");
                else if (len == 4) strcat_s(buf2, "     ");
            }
        }

    }
    printf("%s\n", buf);
    printf("%s\n", buf2);


}

void Graph::print2() {
    int i, pos, pos2;
    char buf[300];
    char buf2[300];
    char buf3[10];
    int max = N * N - 1;
    sprintf_s(buf3, "%d", max);
    int len = strlen(buf3);
    memset(buf3, 0, 10);
    for (i = 0; i < N*N; i++) {
        if (i%N == 0) {
            if (i > 0) {
                printf("%s\n", buf);
                printf("%s\n", buf2);
            }
            memset(buf, 0, 300);
            memset(buf2, 0, 300);
            memset(buf3, 0, 10);
        }
        if (len == 1) sprintf_s(buf3, "%d", i);
        else if (len == 2) sprintf_s(buf3, "%02d", i);
        else if (len == 3) sprintf_s(buf3, "%03d", i);
        else if (len == 4) sprintf_s(buf3, "%04d", i);
        else {
            printf("too big");
            return;
        }
        strcat_s(buf, buf3);
        pos = i / N * (N - 1) + i % N;//(N-1);
        if (i%N != (N - 1)) {
            if (row[pos]) strcat_s(buf, "--");
            else strcat_s(buf, "  ");
        }

        pos2 = (i%N)*(N - 1) + i / N;
        if (i < N*(N - 1)) {
            if (col[pos2]) {
                if (len == 1) strcat_s(buf2, "|  ");
                else if (len == 2) strcat_s(buf2, " |  ");
                else if (len == 3) strcat_s(buf2, " |   ");
                else if (len == 4) strcat_s(buf2, "  |   ");
            }
            else {
                if (len == 1) strcat_s(buf2, "   ");
                else if (len == 2) strcat_s(buf2, "    ");
                else if (len == 3) strcat_s(buf2, "     ");
                else if (len == 4) strcat_s(buf2, "      ");
            }
        }

    }
    printf("%s\n", buf);
    printf("%s\n", buf2);
}

int Graph::edgeCount()
{
    int edge = 0;
    int Count = N * (N - 1);
    for (int i = 0; i < Count; i++) {
        if (row[i]) edge++;
        if (col[i]) edge++;
    }
    return edge;
}

void Graph::path(int st, int en) {

    if (st == en) {
        printf("%d %d", st, en);
        return;
    }

    stack<int> nodes;
    stack<int> edges;
    int Direction[4] = { Left,Up,Right,Down };
    bool *  visited = new bool[N*N];
    int i = 0;
    for (i = 0; i < N*N; i++) visited[i] = false;
    nodes.push(st);
    edges.push(-1);
    visited[st] = true;
    //visit.push(st);

    while (nodes.empty() == false) {
        int n = nodes.top();
        int dir = edges.top();
        int n2 = -1;
        while (dir < 3 && n2 < 0) {//dir={-1,0,1,2}=>{0,1,2,3}
            dir++;
            n2 = findNode2(n, Direction[dir]);
            //是否可通--

            if (n2 >= 0) {
                if (visited[n2]) n2 = -1;
                else break;
            }
        }
        if (n2 < 0) {
            visited[n] = false;//退出该节点了
            nodes.pop();
            edges.pop();
        }
        else {
            edges.pop(); edges.push(dir);
            if (n2 == en) {
                //找到了--
                //stack<int> print = nodes;
                nodes.push(n2);
                print_stack(nodes);
                nodes.pop();

                int dir2 = edges.top();
                if (dir2 == 3) {
                    //退栈--
                    int n3 = nodes.top(); nodes.pop();
                    edges.pop();
                    visited[n3] = false;
                }
            }
            else {
                nodes.push(n2);
                edges.push(-1);
                visited[n2] = true;
            }
        }
    }



    delete visited;

}

void Graph::shortpath(int st, int en)
{
    if (st == en) {
        printf("%d %d", st, en);
        return;
    }
    vector< stack<int> > pathes;//所有的路径
    int path_len = N * N + 1;//路径长度,最大

    stack<int> nodes;
    stack<int> edges;
    int Direction[4] = { Left,Up,Right,Down };
    bool *  visited = new bool[N*N];
    int i = 0;
    for (i = 0; i < N*N; i++) visited[i] = false;
    nodes.push(st);
    edges.push(-1);
    visited[st] = true;
    //visit.push(st);

    while (nodes.empty() == false) {
        //判断当前路径是否超出了最短路径---
        if (nodes.size() > path_len) {
            int n3 = nodes.top();
            visited[n3] = false;
            nodes.pop();
            edges.pop();
            continue;
        }
        int n = nodes.top();
        int dir = edges.top();
        int n2 = -1;
        while (dir < 3 && n2 < 0) {//dir={-1,0,1,2}=>{0,1,2,3}
            dir++;
            n2 = findNode2(n, Direction[dir]);
            //是否可通--

            if (n2 >= 0) {
                if (visited[n2]) n2 = -1;
                else break;
            }
        }
        if (n2 < 0) {
            visited[n] = false;//退出该节点了
            nodes.pop();
            edges.pop();
        }
        else {
            edges.pop(); edges.push(dir);
            if (n2 == en) {
                //找到了--
                //stack<int> print = nodes;
                nodes.push(n2);
                if (nodes.size() < path_len) {
                    pathes.clear();
                    pathes.push_back(nodes);
                    path_len = nodes.size();
                }
                else if (nodes.size() == path_len) {
                    pathes.push_back(nodes);
                }
                printf("path_len=%d\n", path_len);
                nodes.pop();

                int dir2 = edges.top();
                if (dir2 == 3) {
                    //退栈--
                    int n3 = nodes.top(); nodes.pop();
                    edges.pop();
                    visited[n3] = false;
                }
            }
            else {
                nodes.push(n2);
                edges.push(-1);
                visited[n2] = true;
            }
        }
    }



    delete visited;
    print_pathes(pathes);//输出所有的路径
}

void Graph::print_stack(stack<int> nodes)
{
    vector<int> list;
    while (nodes.empty() == false) {
        list.insert(list.begin(), nodes.top());
        nodes.pop();
    }
    bool first = true;
    for (auto val : list)
    {
        if (first) printf("%d", val);
        else printf(" %d", val);
        first = false;
    }
    printf("\n");
}

void Graph::print_stack2(stack<int> path)
{
    bool first = true;
    while (path.empty() == false)
    {
        if (first) printf("%d", path.top());
        else printf(" %d", path.top());
        first = false;
        path.pop();
    }
    printf("\n");
}

void Graph::print_pathes(vector<stack<int>> pathes)
{
    for (auto val : pathes) {
        print_stack(val);
        //printf("\n");
    }
}

void Graph::dfs_start()
{
    stack<int> path;
    bool * visited = new bool[N*N];
    for (int i = 0; i < N*N; i++) visited[i] = false;
    dfs(visited, path, 0);

    print_stack(path);

    delete visited;
}

void Graph::dfs(bool * visited, stack<int>& path, int v)
{
    int Direction[4] = { Left,Up,Right,Down };
    visited[v] = true;
    path.push(v);
    for (int i = 0; i < 4; i++) {
        int n = findNode2(v, Direction[i]);
        if (n >= 0 && visited[n] == false) {
            dfs(visited, path, n);
        }
    }
}

void Graph::shortpath2(int from, int to)
{

    if (from < 0 || from >= N * N || to < 0 || to >= N * N) {
        printf("输入错误。\n"); return;
    }
    if (from == to) {
        printf("%d %d\n", from, to); return;
    }

    vector<Node> nodes;//节点次序
    nodes.resize(N*N);// reserve(N*N);
    vector<int> S, U;
    //U.resize(N*N);// reserve(N*N);
    int i = 0;
    for (i = 0; i < N*N; i++) {
        //将所有的节点-按次序存入nodes
        nodes[i].id = i;
        nodes[i].dis = Juli(from, i);
        if (nodes[i].dis == 1) {//记下前驱节点
            nodes[i].prev.push_back(from);
        }
        if (i != from) U.push_back(i);//其他节点存入U中
    }

    int sindex = 0;
    S.push_back(from);
    //--开始计算过程
    while (U.empty() == false) {
        vector<int> nodelist;//节点编号表,具体情况查nodes
        //int size = S.size();
        for (; sindex < S.size(); sindex++) {
            //查找u中,距离S[index]最近的节点,形成节点表
            int d = MAX_DIS;
            for (int u : U) {
                if (contains(nodes[u].prev, S[sindex])) {//前驱节点是s[i]
                    if (nodes[u].dis < d) {
                        nodelist.clear();
                        nodelist.push_back(u);
                        d = nodes[u].dis;
                    }
                    else if (nodes[u].dis == d && d != MAX_DIS) {
                        nodelist.push_back(u);//同样距离的点
                    }
                }
            }
            //将nodelist的值加入到S中,并从U中去掉
            for (int n : nodelist) {
                S.push_back(n);
                U.erase(std::remove(std::begin(U), std::end(U), n), std::end(U));
            }

            //--用nodelist的值更新-nodes中的距离和前驱
            for (int n : nodelist) {
                //
                //若-以n为中间节点距离更短,则将nodes中的当前节点的前驱修改为n
                for (int u : U) {
                    int d = Juli(n, u);//计算两点间的距离
                    if (d != MAX_DIS) {
                        if (nodes[n].dis + d < nodes[u].dis) {
                            nodes[u].prev.clear();
                            nodes[u].prev.push_back(n);//以n为前驱
                            nodes[u].dis = nodes[n].dis + d;
                        }
                        else if (nodes[n].dis + d == nodes[u].dis)
                        {
                            //同样距离的点
                            nodes[u].prev.push_back(n);
                        }
                    }
                }
            }

            nodelist.clear();
        }
    }
    //遍历nodes,输出所有的路径--
    allpath(from, to, nodes);
}

int Graph::Juli(int from, int to)
{
    if (from == to) return 0;
    if (findNode2(from, Left) == to) return 1;
    if (findNode2(from, Up) == to) return 1;
    if (findNode2(from, Right) == to) return 1;
    if (findNode2(from, Down) == to) return 1;
    return MAX_DIS;
}

bool Graph::contains(vector<int> vec, int val)
{
    int nRet = count(vec.begin(), vec.end(), val);
    return nRet > 0;
}

void Graph::allpath(int from, int to, vector<Node>& nodes)
{
    stack<int> path;
    allpath_dfs(path, to, nodes, from);
}

void Graph::allpath_dfs(stack<int>& path, int to, vector<Node>& nodes, int src)
{
    path.push(to);
    if (to == src) {
        print_stack2(path);
        path.pop();
        return;
    }
    vector<int> prevlist = nodes[to].prev;//前驱节点
    for (int v : prevlist) {
        allpath_dfs(path, v, nodes, src);
    }
    path.pop();
}



int main()
{
    int N = 2;
    printf("输入边的大小 N=");
    scanf_s("%d", &N);
    Graph g(N);
    g.create();//生成迷宫
    g.print();//输出迷宫
    printf("\nedge count=%d\n", g.edgeCount());//迷宫现有的边数
    /* 
    g.test(0);
    g.test(4);
    g.test(10);
    */
    g.dfs_start();//深度优先遍历,证明迷宫的连通性


    int from=0, to=0;
    printf("输入起点:");
    scanf_s("%d", &from);
    printf("输入终点:");
    scanf_s("%d", &to);

    printf("计算从%d到%d的最短路径有:\n",from,to);


    return 0;
}

c++

1个回答

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问
相关内容推荐