【编程训练】路径存储与迷宫寻路 - 指针

请注意,文章中部分理解可能已被笔者废弃,本文最后更新于:3 个月前

问题描述

试图充分运用所学的C++面向对象的知识和封装性,完成一个拓展度高,可编辑型高,有多种兼容性接口的程序。能完成对路径和结点的简历和存储,以此进行最短寻路。达到对所学内容的巩固。

结果展示

可视化结果

代码

注:以下为合并后的代码,根据注释是可以拆分为很多头文件的,更加可读和可编辑。

#include<iostream>
#include<iomanip>
using namespace std;

/*
//point.h
#pragma once
*/
class Point{//模板函数
private:
    int identify;
public:
    Point(int x):identify(x){
        //printf("create Point %d.\n",identify);
    }
    virtual ~Point(){
        //printf("clear Point %d.\n",identify);
    }
    int get_ID()const{return identify;}
};

/*
path.h 与 node.h 的合并,防止相互引用头文件
#pragma once
#include"point.h"
#include<cstdio>
#include<cstdlib>
using namespace std;
*/

#define ll long long
#define ld double
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)

const int INF = 0x3f3f3f3f;

class Node;

class Path{
    friend class Node;
private:
    int val;
    Node *to;
    Path *nxt;
public:
    
    Path* next(){return nxt;}
    int vall(){return val;}
    Node* gono(){return to;}

    Path(int w,Node *go_v,Path *nex=NULL) : val(w) {
        if(w<0)
            printf("[WAR]there are nagetive val way!\n");
        to=go_v;
        nxt=nex;
        printf("create way val %d.\n",w);
    }
    ~Path(){
        //printf("clear way val %d.\n",val);
    }
};

class Node:public Point{
    friend int get_dist(Node &a,Node &b);
    //friend void spfa(Node &u,Refmark &R);
private:
    int x,y;//坐标
    Path *way_head;//出路链表
public:
    bool vis;int dis;Node *Last;bool If_Pass;
    Path* head(){
        return way_head;
    }
    Node(int p,int x,int y):Point(p),x(x),y(y){
        dis=INF;
        vis=0;
        way_head=NULL;
        Last=NULL;
        If_Pass=0;
        printf("create Node %d at (%d,%d), init.\n",get_ID(),x,y);
    }
    ~Node(){
        for(Path *t2,*t = way_head;t!=NULL;t=t2){
            t2=t->nxt;
            delete t;
        }
        //printf("clear Node %d at (%d,%d).\n",get_ID(),x,y);
    }
    int get_dis() const {
        if(dis==-1)
            return INF;
        if(dis<0){
            printf("[ERR]get_dis error!\n");
            exit(0);
        }
        return dis;
    }
    void add_way(Node *to,int val){
        if(way_head==NULL){
            way_head= new Path(val,to);
        }else{
            way_head= new Path(val,to,way_head);
        }
        printf("add way %d to %d, val %d.\n",get_ID(),to->get_ID(),val);
    }
    void print_way(){
        int cnt=0;
        for(Path *t = way_head;t!=NULL;t=t->nxt){
            printf("%d->%d ",get_ID(),t->to->get_ID());
            cnt++;
        }
        printf(". totally %d ways.\n",cnt);
    }
};

int get_dist(Node &a,Node &b){//Point的友元函数 曼哈顿距离
    return abs(a.x-b.x)+abs(a.y-b.y);
}


/*
queue_node.h 队列
#pragma once
#include"graph.h"
*/
class Queue_node_element{
public:
    Node *element;
    Queue_node_element *nxt;

    Queue_node_element(Node &x,Queue_node_element *p=NULL):element(&x),nxt(p){}
};

class Queue_node{
private:
    Queue_node_element *head,*tail;
public:
    Queue_node(){head=tail=NULL;}

    void pop(){//head
        if(head==NULL){
            printf("[ERR]Queue_node pop error!\n");
            exit(0);
        }
        Queue_node_element *cl = head;
        head = head->nxt;   
        delete cl;
    }
    void push(Node &x){//tail
        if(head==NULL){
            head=tail= new Queue_node_element(x,NULL);
            return;
        }
        tail->nxt = new Queue_node_element(x,NULL);
        tail = tail->nxt;
    }
    Node& front(){//head
        if(head==NULL){
            printf("[ERR]Queue_node front error!\n");
            exit(0);
        }
        return *(head->element);
    }
    bool empty(){
        if(head==NULL)
            return true;
        return false;
    }

};

/*
refmark.h
#pragma once
#include"graph.h"
#include"node.h"
#include"path.h"
*/
const int maxn = 1e2;//1e3会过大
const int maxm = 1e2;
class Refmark{
private:
    int n,m;
    Node *ref_p[maxn*maxm];
protected:
    int mark(int x,int y) const {
        return (x-1)*m+y;
    }
    Node* new_ref(int p){
        if(p<1||p>n*m){
            printf("[ERR]new_ref error!\n");
            exit(0);
        }
        if(ref_p[p]!=NULL)
            printf("[WAR]new_ref cover old!\n");
        ref_p[p]=new Node(p,(p-1)/m+1,(p-1)%m+1);
        printf("init new ref %d.\n",p);
        return ref_p[p];
    }
    Node* new_ref(int x,int y){//重载
        return new_ref(mark(x,y));
    }
public:
    Node* ask_ref(int p){//询问对应的Node
        if(p<1||p>n*m){
            printf("[ERR]ask_ref error!\n");
            exit(0);
        }
        if(ref_p[p]==NULL)
            return new_ref(p);
        return ref_p[p];
    }
    Node* ask_ref(int x,int y){//重载
        return ask_ref(mark(x,y));
    }

    bool if_ref(int p){//询问对应的Node是否存在
        if(p<1||p>n*m){
            printf("[ERR]ask_ref error!\n");
            exit(0);
        }
        if(ref_p[p]==NULL)
            return 0;
        return 1;
    }
    bool if_ref(int x,int y){//重载
        return if_ref(mark(x,y));
    }

    Refmark(int n,int m):n(n),m(m){
        FOR(i,1,n*m) ref_p[i]=NULL;
        printf("creat ref %d*%d, init.\n",n,m);
    }
    ~Refmark(){
        FOR(i,1,n*m)
            delete ref_p[i];
        //printf("clear ref.\n");
    }

    void memset_vis(int k=0){
        FOR(i,1,n*m){
            if(ref_p[i]==NULL)
                continue;
            ref_p[i]->vis=k;
        }
        printf("memset ref_p as %d.\n",k);
    }
};

void build_way(Node *u,Node *v,int w=1){
    u->add_way(v,w);
}
void build_way(Refmark &R,int p1,int p2,int w=1){
    R.ask_ref(p1)->add_way(R.ask_ref(p2),w);
}
void build_way(Refmark &R,int x1,int y1,int x2,int y2,int w=1){
    R.ask_ref(x1,y1)->add_way(R.ask_ref(x2,y2),w);
}



/*
spfa.h
#pragma once
#include"refmark.h"
#include"queue_node.h"
*/
void spfa(Node &u,Refmark &R){
    printf("\nbegin spfa at %d.\n",u.get_ID());
    Queue_node q;
    R.memset_vis(0);
    q.push(u);u.vis=1;
    u.dis=0;
    while(!q.empty()){
        Node &u =q.front();
        q.pop();
        u.vis=0;
        for(Path *t = u.head();t!=NULL;t=t->next()){
            Node &v = *(t->gono());
            printf("%d->%d\n",u.get_ID(),v.get_ID());
            if(v.dis>u.dis+t->vall()){
                v.dis = u.dis + t->vall(); 
                v.Last=&u;
            } 
            //printf("%d %d %d\n",v.dis,u.dis,t->vall());
            if(v.vis)
                continue;
            q.push(v);
            v.vis=1;
        }
    }
    printf("end spfa.\n\n");
}

/*
main.cpp
#include"refmark.h"
#include"queue_node.h"
#include"spfa.h"
*/
int main(){
    Node *S,*T;
    int n,m;
    printf("请输入地图大小:");
    cin>>n>>m;
    Refmark R=Refmark(n,m);
    printf("请输入地图路径:");
    while(1){
        int x1,y1,x2,y2;
        cin>>x1;
        if(x1==-1)
            break;
        cin>>y1>>x2>>y2;
        build_way(R,x1,y1,x2,y2);
    }
    int x,y;

    printf("\n请输入出发点坐标:");
    cin>>x>>y;
    S=R.ask_ref(x,y);
    printf("请输入终点坐标:");
    cin>>x>>y;
    T=R.ask_ref(x,y);

    spfa(*S,R);//出发点
    cout<<"ans="<<T->dis<<endl;
    Node *P = T;
    if(T->dis<INF)
        while(P!=S){
            P->If_Pass=1;
            P = P->Last;
        }
    printf("\n");
    FOR(i,1,n){
        FOR(j,1,m){
            if(R.if_ref(i,j)==0){
                cout<<" # ";
            }else{
                //cout<<setw(3)<<R.ask_ref(i,j)->dis;
                if(R.ask_ref(i,j)==S){
                    cout<<" @ ";
                    continue;
                }
                if(R.ask_ref(i,j)==T){
                    cout<<" $ ";
                    continue;
                }
                if(R.ask_ref(i,j)->If_Pass){
                    cout<<" . ";
                    continue;
                }
                cout<<"   ";
            }
        }
        cout<<endl;
    }
    cout<<endl;
    cout<<"END";

    return 0;
}
/*
10 10
1 1 1 2						
1 2 2 2	
2 2 2 3
2 3 3 3	
3 3 4 3	
4 3 4 4	
4 4 4 5			
4 5 5 5			
5 5 6 5			
6 5 7 5	
7 5 7 6	
7 6 7 7	
7 7 7 8
7 8 8 8
8 8 9 8 
-1
1 1
5 5
*/