广度优先搜索

广度优先搜索算法BFS

基本算法

list[1]:= source; {加入初始节点，list为待扩展节点队列}
while(!list.empty())
    sample = list.front()
    list.pop()
    for i:=1 to possible_steps(规则数) do
    begin
            根据sample规则产生新节点new;
            do_new_step(new) {判断新节点是否满足要求,如果符号要求，则将该点push到list队列中}
            将sample标记为已到达
    end

例题

地牢逃脱网易机试题

解体思路

该题描述不是非常清晰，其实简单来说如下：

随机给一个出发点，根据给定的走路规则走，出口可能在地图的任意点，要求：遍历整个地图，找出在哪个点是出口的情况下，离开地图的步数最长(障碍点不可走，可以跨过)

数学公式

不涉及状态转移，没有数学公式

答案示例

#include <string.h>
#include <stdlib.h>
#include <unistd.h>
#include <iostream>
#include <queue>

using namespace std;

int rows;
int cols;
int walk_num;

typedef struct mappoints
{
  int x;
  int y;
  bool reached;//if reached
  bool flag;//if this point can be reached
  int min_walk;
}MAPPOINTS;

typedef struct walks
{
  int x;
  int y;
}WALKS;
queue<MAPPOINTS> need_to_walk;
MAPPOINTS * points  = NULL;
WALKS *walks= NULL;
void print_point(int x, int y)
{
  MAPPOINTS temp = points[x*cols + y];
  cout<<"x: "<< temp.x<<"  y: "<< " min walk: "<< temp.min_walk<<temp.y<<" can be walk: "<<temp.flag<< " reached:"<<temp.reached<<endl;
}
void print_all()
{
  int i , j;
for (i = 0; i< cols ; i++)
  {
    for(j = 0; j < rows; j++)
      print_point(i,j);
  }
}
void deal_points_around(int x, int y)
{
  int i;
  int next_x, next_y;
  MAPPOINTS now = points[x * cols + y];
  for (i = 0; i< walk_num; i++ )
    {
      next_x = walks[i].x + x;
      next_y = walks[i].y + y;
      if (next_y>= 0 && next_x >= 0 && next_x<rows && next_y<cols &&
          points[next_x* cols + next_y].flag &&
          !points[next_x* cols + next_y].reached
         && points[next_x * cols +next_y].min_walk == -1)
        {
          points[next_x* cols + next_y].min_walk = now.min_walk + 1;
          need_to_walk.push(points[next_x* cols + next_y]);
        }
    }
}
void walk_all_point()
{
  while(!need_to_walk.empty())
    {
      MAPPOINTS temp = need_to_walk.front();
      need_to_walk.pop();

      deal_points_around(temp.x, temp.y);
      points[temp.x * cols + temp.y].reached = true;
    }
}
int get_max_step()
{
  int i ,maxstep = 0;
  for (i = 0; i <cols * rows; i ++)
    {
      if (points[i].min_walk == -1 && points[i].flag == true)
        return -1;
    }
  for (i = 0; i< rows * cols; i ++)
    {
      if (maxstep < points[i].min_walk && points[i].flag == true)
        {
          maxstep = points[i].min_walk;
        }
    }
  return maxstep;
}
int main()
{
  string in_str;
  int max_step = 0;
  int i, j;
  cin>>in_str;
  rows = atoi(in_str.c_str());
  cin>>in_str;
  cols = atoi(in_str.c_str());
  points = new MAPPOINTS[rows*cols];
  memset(points,0,sizeof(MAPPOINTS)* rows * cols);
  MAPPOINTS *begin = new MAPPOINTS;
  for (i = 0; i< rows; i++)
    {
      cin>>in_str;
      for (j = 0; j< cols; j++)
        {
          if (in_str.c_str()[j] == '.')
            {
              points[i*cols +j].x = i;
              points[i*cols +j].y = j;
              points[i*cols +j].flag = true;
              points[i*cols +j].min_walk = -1;
            }
          else
            {
              points[i*cols +j].x = i;
              points[i*cols +j].y = j;
              points[i*cols +j].flag = false;
              points[i*cols +j].min_walk = -1;
            }
        }
    }
  cin>>in_str;
  begin->x = atoi(in_str.c_str());
  cin>>in_str;
  begin->y = atoi(in_str.c_str());
  cin>>in_str;
  points[begin->x * cols + begin->y].min_walk = 0;
  need_to_walk.push(points[begin->x * cols + begin->y]);

  walk_num = atoi(in_str.c_str());
  walks = new WALKS[walk_num];

  for (i = 0; i< walk_num; i++)
    {
      cin>>in_str;
      walks[i].x = atoi(in_str.c_str());
      cin>>in_str;
      walks[i].y = atoi(in_str.c_str());
    }
  walk_all_point();
  max_step = get_max_step();
  cout<<max_step<<endl;
  delete []points;
  delete []walks;
  delete begin;
  return 0;
}

要点：

walk_all_point()为重点，他会从初始点开始，一直到搜索完所有可能点
deal_points_around()对应算法描述中do_new_step()
在新节点判断能否加入队列猜了坑，要注意x,y的上限及points[next_x * cols +next_y].min_walk == -1条件

扩展

留点课后练习题

使用go来实现
多加个要求，走路的时候不能跨越障碍物