问题描述:
程序如下：
#include"stdio.h"
#include"stdlib.h"
#define m 4
#define n 4
struct stype
{int x,y
}stack[400]
int mg[m+2][n+2]
int zx[9],zy[9]
void printlj(int TOP)
{int i
for(i=1i<=TOPi++)
{printf("(%d,%d)",stack[i].x,stack[i].y)
}
}
void mglj()
{int i,j,x,y,top,find,v
top=1stack[1].x=1stack[1].y=1find=0mg[1][1]=-1
while(top>=1&&!find)
{x=stack[top].xy=stack[top].y
for(v=1v<=8v++)
{i=x+zx[v]
j=y+zy[v]
if(mg[i][j]==0)
{top++
stack[top].x=i
stack[top].y=j
mg[i][j]=-1
break
}
if(v==8) top--
}
if((stack[top].x ==m)&&(stack[top].y ==n))
{printlj(top)
find=1
}
}
if(!find) printf("no way\n")
}
void main()
{int i,j
for(i=1i<=mi++)
for(j=1j<=nj++)
scanf("%d",&mg[i][j])
for(i=0i<=m+1i++)
{mg[i][0]=1mg[i][n+1]=1}
for(j=0j<=n+1j++)
{mg[0][j]=1mg[m+1][j]=1}
zx[1]=-1zx[2]=-1zx[3]=0zx[4]=1zx[5]=1zx[6]=1zx[7]=0zx[8]=-1
zy[1]=0zy[2]=1zy[3]=1zy[4]=1zy[5]=0zy[6]=-1zy[7]=-1zy[8]=-1
mglj()
}
解析:
我看了一下,算法应该是一样的,下面是我以前用C++写的
相信你能看得懂
/
/迷宫求解
作者:baihacker/
/时间:11.10.2006/
/
/*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=0iscreate=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=0i<row*coli++)
{
*(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=0i<rowi++)
{
for (j=0j<colj++)
{
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=falseresult=0pathlength=row=col=0iscreate=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=0i<r+2i++)
{
for (j=0j<c+2j++)
{
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=0i<pathlengthi++)
{
*(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=0i<pathlengthi++)
{
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=0i<row+2i++)
{
for (j=0j<col+2j++)
{
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=0i<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=_Si<_W+1i++)
{
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=0i<r+2i++)
{
for (j=0j<c+2j++)
{
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
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）