【编程训练】路径存储与迷宫寻路 - 指针
问题描述
试图充分运用所学的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
*/