搜索_广度优先_小迷宫_java左右联通最小步数迷宫-CSDN博客

本文链接：https://blog.csdn.net/zeroDspace/article/details/509585

// Maze.h

#pragma once
#define maxHeight 100
#define maxWidth 100
#define listSize (2*(maxHeight+maxWidth)-4)
class Maze
{
public:
Maze(void);
~Maze(void);
//方法
public:
bool SetMap( char *mapFile );
bool FindPath();
void DrawMap();
void TrackBack();
private:
//属性
private:
//地图布局
int map[maxHeight][maxWidth];
//寻找通路时用到的列表
int graph[maxHeight][maxWidth][3];
int listX[listSize];
int listY[listSize];
int listStep[listSize];
int listHead;
int listTail;
//地图大小
int nHeight;
int nWidth;
//起点、终点坐标
int startX;
int startY;
int endX;
int endY;
};

// Maze.cpp

#include "StdAfx.h"
#include "./maze.h"

#include "stdio.h"
//
//
Maze::Maze(void)
{
for( int i = 0 ; i < maxHeight ; i++ )
{
  for( int j = 0 ; j < maxWidth ; j++ )
   map[i][j] = 9;
}
}
//
//
Maze::~Maze(void)
{
}
//
//
bool Maze::SetMap( char *mapFile )
{
//printf( "from file: %s/n" , mapFile );
int height , width;
FILE *file;
if( (file = fopen( mapFile , "r" ) ) == NULL )
  return false;
//读入地图大小
fscanf( file , "%d %d" , &height , &width );
//printf( "/nheight= %d/nwidth= %d/n" , height , width );
nHeight = height;
nWidth = width;
//读入地图布局
for( int i = 0 ; i < height ; i++ )
{
  for( int j = 0 ; j < width ; j++ )
  {
   char block;
   bool flag;
   do
   {
    fscanf( file , "%c" , &block );
    flag = true;
    if( block == '0' )  //空地
     map[i][j] = 0;
    else if( block == '1' ) //墙壁
     map[i][j] = 1;
    else if( block == '2' ) //起点
    {
     map[i][j] = 2;
     startX = j;
     startY = i;
    }
    else if( block == '3' ) //终点
    {
     map[i][j] = 3;
     endX = j;
     endY = i;
    }
    else
    {
     flag = false;
    }
   }while( !flag );
  }
}
fclose( file );
return true;
}
//
//
bool Maze::FindPath()
{
//初始化 graph
for( int i = 0 ; i < nHeight ; i++ )
{
  for( int j = 0 ; j < nWidth ; j++ )
  {
   for( int k = 0 ; k < 3 ; k++ )
    graph[i][j][k] = 0;
  }
}
//
int step;
int dx[4] = { 0 , 1 , 0 , -1 };
int dy[4] = { -1 , 0 , 1 , 0 };
//走出第一步，即起点
listX[0] = startX;
listY[0] = startY;
listStep[0] = 1;
listHead = 0;
listTail = 0;
step = 1;
graph[startY][startX][0] = step;
//
while( listHead % listSize <= listTail % listSize )
{
  //向四个方向搜索下一步
  for( int i = 0 ; i < 4 ; i++ )
  {
   int sx = listX[ listHead % listSize ];
   int sy = listY[ listHead % listSize ];
   step = graph[sy][sx][0];

   int x = sx + dx[i];
   int y = sy + dy[i];
   if( x < 0 || x >= nWidth || y < 0 || y >= nWidth )
    continue;

   if( graph[y][x][0] == 0 )  //只有没被处理过的
   {
    if( map[y][x] == 3 )  //如果已经到达目的地
    {
     graph[y][x][0] = step + 1;
     graph[y][x][1] = sx;
     graph[y][x][2] = sy;
     TrackBack();
     return true;
    }
    else if( map[y][x] == 0 ) //如果是空地,则，加入到队列中
    {
     listTail++;
     listX[listTail%listSize] = x;
     listY[listTail%listSize] = y;
     graph[y][x][0] = step + 1;
    }
    else
    {
     graph[y][x][0] = -1;
    }
    graph[y][x][1] = sx;
    graph[y][x][2] = sy;
   }
   //
  }//向四个方向搜索结束
  //
  listHead++;
}

return true;
}
//
//
void Maze::TrackBack()
{
int x = endX;
int y = endY;
while( x != startX || y != startY )
{
  map[y][x] = 9;
  int i = graph[y][x][1];
  int j = graph[y][x][2];
  x = i;
  y = j;
}
map[y][x] = 9;
}
//
//
void Maze::DrawMap()
{
for( int i = 0 ; i < nWidth ; i++ )
  printf( "-" );
printf( "/n" );
for( int i = 0 ; i < nHeight ; i++ )
{
  for( int j = 0 ; j < nWidth ; j++ )
  {
   printf( "%d" , map[i][j] );
  }
  printf( "/n" );
}
printf( "/n" );
}
//
//

// findPath.cpp

// findPath.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "conio.h"
#include "Maze.h"

int _tmain(int argc, _TCHAR* argv[])
{
char mazeFile[] = "maze.txt";
Maze maze;
printf( "载入地图.../n" );
if( !maze.SetMap( mazeFile ) )
{
  printf( "%s/n" , "载入地图出错!" );
  getch();
  return false;
}
maze.DrawMap();
if( !maze.FindPath() )
{
  printf( "%s/n" , "没有找到通路" );
}
else
{
  printf( "%s/n" , "已经找到一条路径" );
}
maze.DrawMap();