广度优先遍历解决布线迷宫问题源代码

#include <iostream>
#include <stack>
#include <queue>
using namespace std;

//0--unopccupied
//-5--barricade
//-4--right to left
//-3--up to down
//-2--left to right
//-1--down to up
#define BA -5
#define RL -4
#define LR -2
#define UD -3
#define DU -1

char maze[16][16]={
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, BA, 0, 0, 0, 0},
  {0, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, BA, 0, 0, 0},
  {0, 0, BA, BA, 0, 0, 0, 0, 0, 0, 0, BA, 0, 0, 0, 0},
  {0, 0, 0, BA, 0, 0, 0, 0, BA, BA, BA, 0, 0, 0, 0, 0},
  {0, 0, 0, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, BA, 0, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, BA, BA, 0, 0, 0, 0, 0, 0, BA, BA, BA, 0, 0},
  {0, 0, 0, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0, BA, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, BA, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, BA, 0, 0, 0},
  {0, BA, BA, 0, 0, 0, BA, BA, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, BA, BA, 0, 0, 0, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {BA, BA, BA, 0, 0, BA, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
  {0, 0, 0, BA, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
};

class Position
{
public:
  Position()
  {
    x = 0;
    y = 0;
  }
  
  Position(int _x, int _y)
  {
    x = _x;
    y = _y;
  }
  
  Position& operator=(const Position& ps)
  {
    x = ps.x;
    y = ps.y;
    return *this;
  }
  bool operator==(const Position& ps) const
  {
    return ((x==ps.x)&&(y==ps.y));
  }

  bool operator!=(const Position& ps) const
  {
    return !operator==(ps);
  }
  
  int x;
  int y;
};

bool FindPath(Position start, Position end)
{
  //in fact, the start and end should be verified

  if (start==end)
  {
    cout <<start.x << ", " << start.y << endl;
    return true;
  }
  Position cur, temp;
  queue<Position> mq;
  cur.x = start.x;
  cur.y = start.y;
  
  while (cur!=end)
  {
    if ((cur.y>0)&&(maze[cur.x][cur.y-1]==0))
    {
      maze[cur.x][cur.y-1]=-1;
      temp.x = cur.x; temp.y=cur.y-1;
      mq.push(temp);
    }
    if ((cur.x<16-1)&&(maze[cur.x+1][cur.y]==0))
    {
      maze[cur.x+1][cur.y]=-2;
      temp.x = cur.x+1; temp.y=cur.y;
      mq.push(temp);
    }
    if ((cur.y<16-1)&&(maze[cur.x][cur.y+1]==0))
    {
      maze[cur.x][cur.y+1]=-3;
      temp.x = cur.x; temp.y=cur.y+1;
      mq.push(temp);
    }
    if ((cur.x>0)&&(maze[cur.x-1][cur.y]==0))
    {
      maze[cur.x-1][cur.y]=-4;
      temp.x = cur.x-1; temp.y=cur.y;
      mq.push(temp);
    }
    if (mq.empty())
      return false;
    cur = mq.front();
    mq.pop();
  }
  
  if (cur!=end)
    return false;
  
  while (cur!=start)
  {
    cout << cur.x << ", " << cur.y << endl;
    if (maze[cur.x][cur.y]==-1)
    {
      cur.y = cur.y + 1;
    }
    else if (maze[cur.x][cur.y]==-2)
    {
      cur.x = cur.x - 1;
    }
    else if (maze[cur.x][cur.y]==-3)
    {
      cur.y = cur.y -1;
    }
    else
    {
      cur.x = cur.x + 1;
    }
  }
 
}

int main(int argc, char* argv[])
{
  Position start(0, 0), end(5, 4);
  FindPath(start, end);
}

责任编辑 webmaster

相关链接

欧几里德算法和Stein算法

银行家算法及流程图

字符串匹配之BM算法

汉诺塔非递归算法

空间数据网络渐进传输算法研究

算法的力量:位运算在排序与搜...

markov算法阅读笔记

垃圾邮件和贝叶斯过滤算法