问题描述:
程序如下：
#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.默认出口在右下角
备注:
由于算法原因,这里的所有路径应该是指
介于:
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
c#界面绘制的时候，底层重绘每次会清除画布背景，然后再全部重新绘制，这才是导致闪烁最主要的原因。于是重载消息发送函数 *** 作，禁掉这条消息。代码如下：protected override void WndProc(ref Message m)
{
if (m.Msg == 0x0014) // 禁掉清除背景消息
return
base.WndProc(ref m)
}
// test_03.cpp : 定义控制台应用程序的入口点。//
#include "stdafx.h"
#include<iostream>
using namespace std
struct PosType /* 迷宫坐标位置类型 */
{
int x/* 行值 */
int y/* 列值 */
}
int Maze[5][5] =
{
{0, 0, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
}
#define MAXLENGTH 5
int curstep=1
int a[MAXLENGTH]
int b[MAXLENGTH]
struct SElemType/* 栈的元素类型 */
{
int ord/* 通道块在路径上的＂序号＂ */
PosType seat/* 通道块在迷宫中的＂坐标位置＂ */
int di/* 从此通道块走向下一通道块的＂方向＂(0～3表示东～北) */
}
#define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */
#define STACKINCREMENT 2 /* 存储空间分配增量 */
struct SqStack //SqStack
{
SElemType *base/* 在栈构造之前和销毁之后，base的值为NULL */
SElemType *top/* 栈顶指针 */
int stacksize/* 当前已分配的存储空间，以元素为单位 */
}/* 顺序栈 */
bool InitStack(SqStack *S)
{ /* 构造一个空栈S */
(*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType))
if(!(*S).base)
{
exit(1)/* 存储分配失败 */
}
(*S).top=(*S).base
(*S).stacksize=STACK_INIT_SIZE
return true
}
bool Push(SqStack *S,SElemType e)
{ /* 插入元素e为新的栈顶元素 */
if((*S).top-(*S).base>=(*S).stacksize) /* 栈满，追加存储空间 */
{
(*S).base=(SElemType *)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType))
if(!(*S).base)
{
exit(1)/* 存储分配失败 */
}
(*S).top=(*S).base+(*S).stacksize
(*S).stacksize+=STACKINCREMENT
}
*((*S).top)++=e
return true
}
bool StackEmpty(SqStack S)
{ /* 若栈S为空栈，则返回TRUE，否则返回FALSE */
if(S.top==S.base)
return true
else
return false
}
bool Pop(SqStack *S,SElemType *e)
{ /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR */
if((*S).top==(*S).base)
return false
*e=*(--(*S).top)
return true
}
bool Pass(PosType b)
{ /* 当迷宫m的b点的序号为1(可通过路径)，return true, 否则，return false */
if(Maze[b.x][b.y]==1)
return true
else
return false
}
void FootPrint(PosType a)
{ /* 使迷宫m的a点的序号变为足迹(curstep) */
Maze[a.x][a.y]=curstep
}
PosType NextPos(PosType c,int di)
{ /* 根据当前位置及移动方向，返回下一位置 */
PosType direc[4]={{0,1},{1,0},{-1,0},{0,-1}}
/* 移动方向,依次为东南西北 */
c.x+=direc[di].x
c.y+=direc[di].y
return c
}
void MarkPrint(PosType b)
{ /* 使迷宫m的b点的序号变为-1(不能通过的路径) */
Maze[b.x][b.y]=-1
}
void Print(int x,int y)
{ /* 输出迷宫的解 */
int i,j
for(i=0i<xi++)
{
for(j=0j<yj++)
cout<<"\t"<<Maze[i][j]
cout<<endl
}
}
bool MazePath(PosType start,PosType end)
{
SqStack S
SElemType e
InitStack(&S)
a[0]=start.x
b[0]=start.y
PosType curpos=start
do
{
if(Pass(curpos))
{ /* 当前位置可以通过，即是未曾走到过的通道块 */
FootPrint(curpos)/* 留下足迹 */
a[curstep]=curpos.x
b[curstep]=curpos.y
e.di=0
e.ord=curstep
e.seat.x=curpos.x
e.seat.y=curpos.y
Push(&S,e)
// printf("PUSH1 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord)
if(curpos.x==end.x&&curpos.y==end.y)
return true
curpos=NextPos(curpos,e.di)
curstep++
}
else
{ /* 当前位置不能通过 */
if(!StackEmpty(S))
{
Pop(&S,&e)/* 退栈到前一位置 */
// printf("POP1 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord)
curstep--
while((e.di==3) &&(!StackEmpty(S)))
{
MarkPrint(e.seat)
Pop(&S,&e)
printf("POP2 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord)
curstep--
}
if(e.di<3) /* 没到最后一个方向(北) */
{
e.di++
// e.seat.x=curpos.x
// e.seat.y=curpos.y
Push(&S,e)
// printf("PUSH2 %d,%d,%d,%d \n",e.seat.x,e.seat.y,e.di,e.ord)
curpos=NextPos(e.seat,e.di)
curstep++
}
}
}
}while(!StackEmpty(S))
return false
}
int _tmain(int argc, _TCHAR* argv[])
{
PosType begin,end
begin.x = 1
begin.y = 1
end.x = 3
end.y = 3
if(MazePath(begin,end)) /* 求得一条通路 */
{
cout<<"此迷宫从入口到出口的一条路径如下:"<<endl
Print(5,5)/* 输出此通路 */
for(int i=1i<curstepi++)
{
cout<<"("<<a[i]<<","<<b[i]<<")"<<"->"
}
cout<<"("<<a[curstep]<<","<<b[curstep]<<")"<<endl
}
else
{
cout<<"此迷宫没有从入口到出口的路径"<<endl
}
system("pause")
return 0
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）