关于C语言的问题,高手进
发布网友
发布时间：2022-04-29 14:54
共2个回答
热心网友
时间：2023-10-13 02:47
/////////////////////////
/////////迷宫求解////////
//////作者:hacker/////
/////时间:11.10.2006/////
/////////////////////////
//Migong.h
//利用栈进行回溯
/*class:
Matrix:矩阵类
offsets:搜索偏移
enum directions:四个方向
struct item:搜索节点
Migong:迷宫类
1.创建一个Migong对象
2.使用用Create方法输入数据
3.使用Solve方法进行求解
4.ShowSolve方法显示解
5.可以重复使用Create方法
6.入口只能在左上角
7.默认出口在右下角
ShowAllPath:穷举所有的路径
备注:
由于算法原因,这里的所有路径应该是指
介于:
a.如果两条路存在某个点不同那么就是不同的路
b.如果在一条路中去掉一个或者一个以上的圈,那么他们是同一条路
之间意义上的路
*/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#ifndef MIGONG_H
#define MIGONG_H
///////////////////
///////矩阵类//////
///////////////////
class Matrix{
int* m;
int row, col;
bool iscreate;
public:
Matrix(){m=0;iscreate=false;};
~Matrix() {Release();};
bool Create(int, int);
int& operator () (int, int);
int GetRow(){return row;};
int GetCol(){return col;};
void Release();
void Show(char, char );
};
bool Matrix::Create(int r, int c)
{
if( r<=0 || c<=0) return false;
Release();
row = r;
col = c;
m = new int[row*col];
for (int i=0;i<row*col;i++)
{
*(m+i) = 0;
}
iscreate = true;
return true;
}
int& Matrix::operator ()(int r, int c)
{
return *(m+r*col+c);
}
void Matrix::Release()
{
if (iscreate)
{
row = col = 0;
if (m) delete[] m;
m = 0;
}
iscreate = false;
}
void Matrix::Show(char blk='#', char nblk=' ')
{
int i, j;
for (i=0;i<row;i++)
{
for (j=0;j<col;j++)
{
if (*(m+i*col+j) == 0)
cout<<nblk;
else
cout<<blk;
}
cout<<endl;
}
}
/////////////////////////////
////迷宫相关数据结构的定义///
/////////////////////////////
struct offsets{
int a, b;
};
enum directions{
_S = 0,
_E,
_N,
_W
};
struct item{
int row, col, dir;
};
class Migong{
static offsets move[4];
Matrix maze;
Matrix mark;
int row;
int col;
int desr;
int desc;
stack<item> stk;
bool iscreate;
int pathlength;
bool GetPath();
bool IsInPath(int, int);
public:
Migong(){issolved=false;result=0;pathlength=row=col=0;iscreate=false;};
~Migong(){Release();};
bool Create(int* , int , int , int , int );
void Solve();
void Release();
void OutputMaze();
void ShowSolve(char, char );
public:
bool issolved;
item* result;
};
offsets Migong::move[4]={ {1, 0}, {0, 1},
{-1, 0}, {0, -1}};
////////////////////////////
//迷宫数据应该是不含边框的//
////////////////////////////
bool Migong::Create(int* m, int r, int c, int desrow=-1, int descol=-1)
{
if (r<=0 || c<=0) return false;
Release();
if (desrow==-1 || descol==-1)
{
desr = r;
desc = c;
}
else
{
desr = desrow;
desc = descol;
}
row = r;
col = c;
maze.Create(r+2, c+2);
mark.Create(r+2, c+2);
int i, j;
for (i=0;i<r+2;i++)
{
for (j=0;j<c+2;j++)
{
if (j==0 || j==c+1 || i==0 || i==r+1)
{
mark(i, j) = maze(i, j) = 1;
}else
{
mark(i, j) = 0;
maze(i, j) = m[((i-1)*col+j-1)];
}
}
}
return iscreate = true;
}
bool Migong::GetPath()
{
mark(1,1) = 1;
item temp;
temp.col = 1;
temp.row = 1;
temp.dir = _S;
stk.push(temp);
while (!stk.empty())
{
temp = stk.top();
stk.pop();
int i = temp.row;
int j = temp.col;
int d = temp.dir;
while (d<4)
{//根据当前点的状态确定下一个搜索点
int g = i + move[d].a;
int h = j + move[d].b;
if (g==desr && h==desc)
{
return true;
}
//如果这个点不是障碍点且没有被搜索过那么可以对这个点进行搜索
if (maze(g, h)==0 && mark(g, h)==0)
{
mark(g, h) = 1;
temp.row = g;
temp.col = h;
temp.dir = d+1;
stk.push(temp);
i = g;
j = h;
d = _S;//对一下个点进行搜索
}
else d++;
}
}
return false;
}
void Migong::Solve()
{
issolved = GetPath();
if (issolved)
{
pathlength = stk.size();
result = new item[pathlength];
for (int i=0;i<pathlength;i++)
{
*(result+i) = stk.top();
stk.pop();
// cout<<"("<<(*(result+i)).row<<","<<(*(result+i)).col<<")"<<endl;
}
}
while (!stk.empty())
stk.pop();
}
void Migong::Release()
{
if (iscreate)
{
maze.Release();
mark.Release();
row=col=0;
if (result)
delete [] result;
result = 0;
while (!stk.empty())
stk.pop();
}
iscreate = false;
issolved = false;
pathlength = 0;
}
void Migong::OutputMaze()
{
if (!iscreate) return;
maze.Show();
}
bool Migong::IsInPath(int r, int c)
{
if (!iscreate || !issolved)
return false;
item temp;
for (int i=0;i<pathlength;i++)
{
temp = *(result+i);
if ((temp.row==r) && (temp.col==c))
return true;
}
return false;
}
void Migong::ShowSolve(char blk='#',char s='o')
{
if (!iscreate) return;
if (!issolved)
{
cout<<"无解"<<endl;
}
else
{
int i, j;
for (i=0;i<row+2;i++)
{
for (j=0;j<col+2;j++)
{
if ((i==1 && j==1) || (i==desr && j==desc))
{
cout<<s;
}
else if (maze(i, j) == 1)
{
cout<<blk;
}else
{
if (IsInPath(i, j))
cout<<s;
else
cout<<' ';
}
}
cout<<endl;
}
}
}
//////////////////////
//////穷举所有路径////
//////////////////////
offsets move[4]={ {1, 0}, {0, 1},
{-1, 0}, {0, -1}};
struct node
{
int row,col;
};
vector<node> path;
int count;
bool IsReachable( Matrix& maze, Matrix& mark, node beg, node des)
{
if (beg.row==des.row&&beg.col==des.col)
{//如果达到的话那么显示路径
count++;
cout<<"第"<<count<<"条路径:"<<endl;
for (int i=0;i<path.size();i++)
cout<<"("<<path[i].row<<","<<path[i].col<<")";
cout<<"("<<des.row<<","<<des.col<<")";
cout<<endl;
return false;
}
if (maze(beg.row, beg.col)==1 || mark(beg.row, beg.col)==1)
{
return false;
}
path.push_back(beg);
mark(beg.row, beg.col) = 1;
node nextnode;
for (int i=_S;i<_W+1;i++)
{
nextnode.row = beg.row + move[i].a;
nextnode.col = beg.col + move[i].b;
IsReachable(maze, mark, nextnode, des);
}
path.resize(path.size()-1);
mark(beg.row, beg.col) = 0;
return false;//如果不是穷举的话应该根据for循环的结果重新设置返回值
}
/*
参数maze,mark为迷宫长宽均加二的矩阵
desr,desc为出口点
*/
void FindAllPath( Matrix& maze, Matrix& mark, int desr, int desc)
{
node first, last;
first.row = 1;
first.col = 1;
last.row = desr;
last.col = desc;
IsReachable(maze, mark, first, last);
path.clear();
}
/*
m迷宫矩阵数据
r,c行和列的大小
desr,desc目标位置
*/
void ShowAllPath(int* m, int r, int c, int desr=-1, int desc=-1)
{
Matrix maze, mark;
maze.Create(r+2, c+2);
mark.Create(r+2, c+2);
if (desr==-1 || desc==-1)
{
desr = r;
desc = c;
}
int i, j;
for (i=0;i<r+2;i++)
{
for (j=0;j<c+2;j++)
{
if (j==0 || j==c+1 || i==0 || i==r+1)
{
mark(i, j) = maze(i, j) = 1;
}else{
mark(i, j) = 0;
maze(i, j) = m[((i-1)*c+j-1)];
}
}
}
count = 0;
FindAllPath(maze, mark, desr, desc);
maze.Release();
mark.Release();
}
#endif
//main.cpp
#include <iostream>
#include "Migong.h"
using namespace std;
int mg[]={
0,0,1,0,0,0,1,0,//1
0,0,1,0,0,0,1,0,//2
0,0,0,0,1,1,0,1,//3
0,1,1,1,0,0,1,0,//4
0,0,0,1,0,0,0,0,//5
0,1,0,0,0,0,0,1,//6
0,1,1,1,1,0,0,1,//7
1,1,0,0,0,1,0,1,//8
1,1,0,0,0,0,0,0,//9
};
void main()
{
Migong m;
m.Create(mg, 9, 8);
m.OutputMaze();
m.Solve();
m.ShowSolve();
ShowAllPath(mg,9,8,9,8);
}
2.任意两点的最短路
class Matrix
{
bool IsCreated;
int* data;
int row;
int col;
public:
Matrix(){IsCreated = false;row = 0; col = 0; data = 0;};
~Matrix(){if (data!=0) delete [] data;};
bool Create(int r, int c, int n);
int& operator () (int r, int c);
};
bool Matrix::Create(int r, int c, int n = 0)
{
if ( IsCreated)
return false;
if ( (row = r) <=0 || (col = c) <=0)
return false;
data = new int[row*col];
int i,j;
for (i=0;i<row;i++)
for (j=0;j<col;j++)
data[i*col+j] = n;
IsCreated = true;
return true;
}
int& Matrix::operator()(int r, int c)
{
return data[r*col+c];
}
jingdian//Matrix类,存储点
dist//Matrix类,存储任意两点间的距离
MAX_DIST//一个大数,大于任意两点间的距离,当两点间没有路的时候设为它
bestdist//Matrix类,存储任意两点的最近距离
bestpath//Matrix类,i到j的最短路为i.......bestpath(i,bestpath(i,pbestpath(i,j))), bestpath(i,pbestpath(i,j)), j bestpath(i,j)表示i到j的最短路中j的前一个结点号
void GetBestPath()
{
int n = jingdian.size();
int i, j, k;
bestdist.Create(n, n);
bestpath.Create(n, n);
for (i=0;i<n;i++)
for (j=0;j<n;j++)
{
if ( (bestdist(i,j) = dist(i,j)) == -1)
bestdist(i,j) = MAX_DIST;
if ( i!=j && bestdist(i,j)<MAX_DIST )
bestpath(i,j) = i;
else
bestpath(i,j) = -1;
}
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (bestdist(i,k)+bestdist(k,j) < bestdist(i,j))
{
bestdist(i,j) = bestdist(i,k)+bestdist(k,j);
bestpath(i,j) = bestpath(k,j);
}
}
热心网友
时间：2023-10-13 02:48
#include <stdlib.h>
#include <string.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
typedef int Status;
#define IN99v_SIZE 100 //存储空间初始分配量
#define INCREMENT 30 //存储空间分配增量
#define MAXLEN 100//迷宫包括外墙最大行列数目
typedef struct{ //迷宫中row行col列的位置
int row;
int col;
}PostType;
typedef struct{
int ord; //当前位置在路径上的序号
PostType seat;//当前坐标
int di; //往下一坐标的方向
}SElemType; //栈元素类型
typedef struct{
SElemType* base;//栈基址,构造前销毁后为空
SElemType* top;//栈顶
int stackSize; //栈容量
}Stack; //栈类型
Status InitStack(Stack &S){ //构造空栈s
S.base=(SElemType*)malloc(IN99v_SIZE *sizeof(SElemType));
if(!S.base)
exit(OVERFLOW);//存储分配失败
S.top=S.base;
S.stackSize=IN99v_SIZE;
return OK;
}//InitStack
Status StackEmpty(Stack S){
//若s为空返回TRUE,否则返回FALSE
if(S.top==S.base)
return TRUE;
return FALSE;
}//StackEmpty
Status Push(Stack &S,SElemType e){
//插入元素e为新的栈顶元素
if(S.top-S.base >=S.stackSize){//栈满，加空间
S.base=(SElemType *)realloc(S.base,(S.stackSize+INCREMENT)*sizeof(SElemType));
if(!S.base)
exit(OVERFLOW); //存储分配失败
S.top=S.base+S.stackSize;
S.stackSize+=INCREMENT;}
*S.top++=e;
return OK;
}//push
Status Pop(Stack &S,SElemType &e){//若栈不空删除栈//顶元素用e返回并返回OK，否则返回ERROR
if(S.top==S.base)
return ERROR;
e=*--S.top;
return OK;
}//Pop
Status DestroyStack(Stack &S){//销毁栈S,
free(S.base);
S.top=S.base;
return OK;
}//DestroyStack..
typedef struct{
int row;
int col;
char adr[MAXLEN][MAXLEN];//可取' ''\001' '\002' '#'
}MazeType; //迷宫类型
Status InitMaze(MazeType &maze){
//初始化迷宫若成功返回TRUE,否则返回FALSE
int m,n,i,j;
maze.row=0;
maze.col=0;
while(maze.row>50 || maze.row<5){
printf("请输入所要创建迷宫的行数:");
scanf("%d",&maze.row); //迷宫行数
if(maze.row>=50 || maze.row<=5)
printf("行数必须是5-50之间的整数\n");
continue;
if(maze.row<=50 && maze.row>=5)
break;}
while(maze.col>50 || maze.col<5){
printf("请输入所要创建迷宫的列数:");
scanf("%d",&maze.col);
if(maze.col>=50 || maze.col<=5)
printf("列数必须是5-50之间的整数\n");
continue;
if(maze.col<=50 && maze.col>=5)
break;}
for(i=0;i<=maze.col+1;i++){//迷宫行外墙
maze.adr[0][i]='#';
maze.adr[maze.row+1][i]='#';}//for
for(i=0;i<=maze.row+1;i++){//迷宫列外墙
maze.adr[i][0]='#';
maze.adr[i][maze.col+1]='#';}
for(i=1;i<=maze.row;i++)
for(j=1;j<=maze.col;j++)
maze.adr[i][j]=' ';//初始化迷宫
printf("下面请输入你的障碍坐标\n注：当设置好障碍坐标后，输入数字0 后结束。");
do{ printf("\n请输入障碍的横坐标: ");
scanf("%d",&m);
if(m==0)break;
if(m>maze.row){
printf("输入的数不能超过最大行数\n");
continue;}
if(m<0){
printf("输入的数不能比1小\n");
continue;}
printf("请输入障碍的纵坐标: ");
scanf("%d",&n);
if(n==0)break;
if(n>maze.col){
printf("输入的数不能超过最大列数\n");
continue;}
if(n<0){
printf("输入的数不能比1小\n");
continue;}
maze.adr[m][n]='#';//迷宫障碍用'#'标记
}while(m!=0||n!=0);//while
return OK;
}//InitMaze
Status Pass(MazeType maze,PostType curpos){
//当前位置可通则返回TURE,否则返回FALSE
if(maze.adr[curpos.row][curpos.col]==' ')//可通
return TRUE;
else
return FALSE;
}//Pass
Status FootPrint(MazeType &maze,PostType curpos){
//若走过并且可通返回TRUE,否则返回FALSE
//在返回之前销毁栈S
maze.adr[curpos.row][curpos.col]='\001';//"\001"表示可通
return OK;
}//FootPrint
PostType NextPos(PostType &curpos,int i){
//指示并返回下一位置的坐标
PostType cpos;
cpos=curpos;
switch(i){ //1.2.3.4分别表示东,南,西,北方向
case 1 : cpos.col+=1; break;
case 2 : cpos.row+=1; break;
case 3 : cpos.col-=1; break;
case 4 : cpos.row-=1; break;
default: exit(ERROR);}
return cpos;
}//Nextpos
Status MarkPrint(MazeType &maze,PostType curpos){
//曾走过但不是通路标记并返回OK
maze.adr[curpos.row][curpos.col]='\002';//"\002"表示曾走过但不通
return OK;
}//MarkPrint
Status MazePath(MazeType &maze,PostType start,PostType _end){
//若迷宫maze存在从入口start到_end的通道则求得一条存放在栈中
//并返回TRUE,否则返回FALSE
Stack S;
PostType curpos;
int curstep;//当前序号,1.2.3.4分别表示东,南,西,北方向
SElemType e;
InitStack(S);
curpos=start; //设置"当前位置"为"入口位置"
curstep=1; //探索第一步
do{
if(Pass(maze,curpos)){//当前位置可以通过,
//即是未曾走到过的通道
FootPrint(maze,curpos);//留下足迹
e.ord=curstep;
e.seat=curpos;
e.di=1;
Push(S,e); //加入路径
if(curpos.row==_end.row&& curpos.col==_end.col)
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return TRUE; //到达出口
else{
curpos=NextPos(curpos,1);
//下一位置是当前位置的东邻
curstep++; //探索下一步
}//else
}//if
else{ //当前位置不通
if(!StackEmpty(S)){
Pop(S,e);
while(e.di==4
&& !StackEmpty(S)){
MarkPrint(maze,e.seat);
Pop(S,e);
//留下不能通过的标记,并退一步
}//while
if(e.di < 4){
e.di++;//换下一个方向探索
Push(S,e);
curpos=NextPos(e.seat,e.di);//设定当前位置是该
//新方向上的相邻
}//if
}//if
}//else
}while(!StackEmpty(S));
if(!DestroyStack(S))//销毁失败
exit(OVERFLOW);
else
return FALSE;
}//MazePath
void PrintMaze(MazeType &maze){
//将标记路径信息的迷宫输出到终端(包括外墙)
int i,j;
printf("\n迷宫路径如下图所示:\n\n");
printf(" ");
for(i=0;i<=maze.col+1;i++)//打印列数名
printf("%4d",i);
printf("\n\n");
for(i=0;i<=maze.row+1;i++){
printf("%2d",i);//打印行名
for(j=0;j<=maze.col+1;j++)
printf("%4c",maze.adr[i][j]);//输出迷宫//当前位置的标记
printf("\n\n");
}
}//PrintMaze
void main(){ //主函数
MazeType maze;
PostType start,_end;
char cmd;
do{ system("cls");
printf("##########################################################################\n");
printf("# #\n");
printf("# 迷宫求解 #\n");
printf("# #\n");
printf("# 姓名： 班级： 学号： #\n");
printf("# #\n");
printf("# #\n");
printf("# 欢迎使用 copy left #\n");
printf("# #\n");
printf("# #\n");
printf("##########################################################################\n");
if(!InitMaze(maze)){ //初始化并创建迷宫
printf("\nInitialization errors!!!\n");
exit(OVERFLOW); //初始化错误
}
do{ //输入迷宫入口坐标
printf("\n输入迷宫入口坐标: ");
scanf("%d%d",&start.row,&start.col);
if(start.row>maze.row || start.row<1|| start.col>maze.col || start.col<1)
{ printf("\n入口错误!!!\n");
continue;}
}while(start.row>maze.row || start.row<1 || start.col>maze.col || start.col<1);
do{ //输入迷宫出口坐标
printf("\n输入迷宫出口坐标: ");
scanf("%d%d",&_end.row,&_end.col);
if(_end.row>maze.row || _end.row<1 || _end.col>maze.col || _end.col<1){
printf("\n出口错误!!!\n");
continue;}
}while(_end.row>maze.row || _end.row<1 || _end.col>maze.col || _end.col<1);
if(!MazePath(maze,start,_end))//迷宫求解
printf("\n此路不通!!!\n");
else
PrintMaze(maze);//打印路径
printf("\n如果继续请输入y，退出请输入n: ");
scanf("%s",&cmd);
}while(cmd=='y' || cmd=='Y');
}//main
迷宫求解问题用C＋＋编写.
