广搜回顾

上一篇博客我已经和大家从整体上分析了广搜bfs，深搜dfs和递归，对于广搜，举了一道例题，就是noj的加一乘二平方，当时借助这个题目就和大家分享了bfs求解的一般模式----取出根节点u，扩展u，当然使用的是while循环

这个题目非常简单，没有难度，因为这里的分支都确定好了，就三种分支；并且在每一个结点处的状态也很简单，就简单的一个步数，用int记录就可以了

广搜题目

首先和大家分享一个非常有趣的问题，八数码问题，这不是一个数学问题，而是一个计算机问题，类似于我们小时候玩的推箱子，拼图游戏，一起来看一下

noj1541八数码问题

题目来源 ： noj 1541

题目描述：

在九宫格里放在1到8共8个数字还有一个是空格，与空格相邻的数字可以移动到空格的位置，问给定的状态最少需要几步能到达目标状态（用0表示空格）：
1 2 3
4 5 6
7 8 0

题目要求即样例

输入：

输入一个给定的状态。

输出：

输出到达目标状态的最小步数。不能到达时输出-1。

输入样例：

1 2 3
4 0 6
7 5 8

输出样例：

2

题目分析

看到题目，先看题目的输出：输出的是步数，---- 再看一下题目的描述，要求的是移动数字，每一个都有多种移动方式，—一下子就有思路了，步数加上题目的树结构描述----广搜首选了，这是根据我们之前的经验推出来的题目的解决办法

好了，也许会问，哪里来的树结构？0可以移动到于与之相邻的位置，这里样例中的0有两个位置可以移动，6和8的位置；到了6的位置，又有两个位置可以移动3和5的位置；到了5的位置，有4个位置可以移动······形成了一个树结构，那求步数就简单了嘛，一层一层搜索，找到目标状态，输出层号就可

完全离不开我们之前分析的bfs的一般结构，还是用队列来存储每一个结点的状态；这里的每个结点所对应的状态是一个九宫格？

这怎么弄？你不可能用一个二维数组来存储状态吧，那如何比较？难道用矩阵的方式？所以用二维数组是不现实的，这里使用的是将九宫格转化为一串数字存储，那八皇后问题，不也是降维了，所以这里降维是肯定的

所以就转为一串数字执行

那按照bfs一般思路，那就是用两个数组，一个记录步数，一个记录是否用过

int used[1000000000];//最大还是九位数
int step[1000000000];//记录步数
int mover[4] = { -1,0,+1,0 };//上左下右移动
int movec[4] = {0,-1,0,+1};

但是按照常识就知道这超出范围了，这可又怎么办，每一个状态都是一个九位数，所以这里就用到了之前java中分析的映射map

那这里要如何？

使用c++库中的map就可以了，map映射为一一映射，一个键只对应一个值，和java一样，键是set，所以只允许出现一次，否则添加的时候就会自动删除，这里使用C++库中的mag.count方法，为0才让它继续运行. 这里它就相当于之前的两个数组

map<int, int> useandstepmap;//一一映射关系，并且和set一样，只能出现一次
int mover[4] = { -1,0,+1,0 };//上左下右移动
int movec[4] = {0,-1,0,+1};

题解代码【注解详细】—理解BFS

#include<iostream>
#include<queue>
#include<map>

using namespace std;

queue<int> q; //还是一个队列，来记录位置
map<int, int> useandstepmap;//一一映射关系，并且和set一样，只能出现一次
int mover[4] = { -1,0,+1,0 };//上左下右移动
int movec[4] = {0,-1,0,+1};
 
int inputdata()
{
	int t = 0;//将二维数组转化为一串10进制数
	int num;
	for (int i = 0; i < 9; i++)
	{
		cin >> num;
		t = t * 10 + num;//这样最开始输入的数据就是最高位
	}
	return t;
}
void init(int root)
{
	useandstepmap[root] = 0;
	q.push(root); //步骤一模一样
}

int moveto(int u, int dire)
{//先解码，再转码，不然不好操作
	int loadnum;
	loadnum = u;//要不断变化
	int statu[3][3];//最开始转码是从左上到右下，解码反过来
	int row, col;//记录初始空格位置
	int r, c; //记录需要移动的位置
	for (int i = 2; i >= 0; i--)
	{
		for (int j = 2; j >= 0; j--)
		{
			statu[i][j] = loadnum % 10;
			loadnum = loadnum / 10;
			if (statu[i][j] == 0)
			{
				row = i;
				col = j;
			}
		}
	}
	r = row + mover[dire];
	c = col + movec[dire];//这里因为固定，就不需要讨论，在创建数组时就讨论好了
	//移动空格
	statu[row][col] = statu[r][c];
	statu[r][c] = 0;
	//转码
	int v = 0;
	for (int i = 0; i < 3; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			v = v * 10 + statu[i][j];
		}
	}
	return v;
}

bool canMove(int u, int dire)
{
	int loadnum = u;
	//转码判断位置是否合法
	int statu[3][3];
	int row, col;//记录空格位置
	for (int i = 2; i >= 0; i--)
	{
		for (int j = 2; j >= 0; j--)
		{
			statu[i][j]= loadnum % 10;
			loadnum = loadnum / 10;
			if (statu[i][j] == 0)
			{
				row = i;
				col = j;
			}
		}
	}
	row = row + mover[dire];
	col = col + movec[dire];
	int v;
	v = moveto(u, dire);
	if (row < 3 && row >= 0 && col >= 0 && col < 3)//判断使用就在map中
	{
		return true;
	}
	return false;
}

int bfs()
{//一般情况就是有4个子支可以移动
	while (!q.empty())
	{
		int u, v;
		//1.取出结点u
		u = q.front();
		q.pop();
		//扩展u{还是使用for循环来表示子支}
		for (int i = 0; i < 4; i++)//0 1 2 3 上左下右
		{
			if (canMove(u, i))//移动的状态
			{
				v = moveto(u, i);
				if (v == 123456780)
				{
					return useandstepmap[u] + 1;
				}
				if (useandstepmap.count(v) == 0)
				{
					useandstepmap[v] = useandstepmap[u] + 1;
					q.push(v);
				}
			}
		}
	}
}

int main() 
{//这个题目只是状态复杂了一些，其他就是一般的bfs
	int root,step;
	root = inputdata();//初始状态
	init(root); //初始化一样
	step = bfs();
	cout << step << endl;
}

我使用c++的原因是oj上不支持java，c++用起来也很方便，特别是这里的map成功解决一维数组越界问题

noj1652 僵尸来了

其实我准备出的是推箱子这个游戏的，但是其实推箱子也和上面的移动差不多，并且C站里也有相应题目了，所以这里分享1652这个题目，因为这是oj里才出不久的题目，还没有详解

题目描述

僵尸要来佳佳家做客了，佳佳把花园布置了一下，你拿到了花园的地图（以二维矩阵的形式表示）以及起点和佳佳家的位置。花园里某些位置有地刺，僵尸过的时候每次需要消耗一个单位的生命值，僵尸有一定数量的生命值，看看最聪明的僵尸能否在天亮前到达你的家里？能的话，最少花费多少时间。

题目要求及样例

输入：

输入的第一行包含三个整数：m，n，t。代表m行n列的地图和僵尸的生命值t。m,n都是小于200的正整数，t是小于10的正整数，第2行开始的m行是m行n列的花园地图，其中!代表起点，+表示佳佳家。*代表通路，w代表地刺。

输出：

输出僵尸到达佳佳家最少需要花费的时间。如果无法到达，则输出-1。

输入样例：

4 4 2
w!ww
**ww
www+
****

输出样例：

6

题目分析

又又又是一个移动问题，要求输出的是最少到达的时间，其实就是最少的到达步数，样例输出的结果为6，分析一下，僵尸这里有2点的生命值，那么路径就是先一直往下3步，右走2步，上走一步，就是6步，就是这样子，僵尸行走的方向还是有4个，上下左右，和上面的拼图一样，

明确使用bfs，接下来分析状态，上一个题目的状态就是二维数组的一个新的形态，步数为因变量，所以记录形态就使用一维数组，只是因为越界，所以，这里就把used一起纳入组成map，v为键，used为值，使用map.count实现了自动避开used，这里的状态复杂了一点，因为这里每个状态就是其目前所处坐标还有其生命值，按照dp的话，这里应该是一个三位dp

如果是dp就使用step【row】【col】【hp】来表示状态的步数

这里我们使用深搜，那就使用结构体表示结点就可以了

其他的基本思路，还是套用之前博客中的bfs的一般模式，这里只是需要注意细节，吃掉第一行的回车，输入时

题目代码（注解详细）

#include<iostream>
#include<queue>

using namespace std;


struct node {
	int row;
	int col;
	int hp;
};

node start, target;//记录结点
int m, n, t;
char  garden[200][200];//二维数组【花园】
queue<node> q; //结点队列
int used[200][200][10];
int step[200][200][20];//和之前一样使用记录步数

int mover[4] = { -1,0,+1,0 };//上左下右
int movec[4] = { 0,-1,0,+1 };

void input()//忘记吃掉第一行的回车
{
	cin >> m >> n >> t;
	start.hp = t;
	cin.get();
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			garden[i][j] = cin.get();
			if (garden[i][j] == '!')
			{
				start.row = i;
				start.col = j;
			}
			if (garden[i][j] == '+')
			{
				target.row = i;
				target.col = j;
			}
		}
		cin.get();
	}
}

void init(node start)
{
	for (int i = 0; i < 200; i++)
	{
		for (int j = 0; j < 200; j++)
		{
			for (int k = 0; k < 10; k++)
			{
				step[i][j][k] = 10000;
			}
		}
	}
	used[start.row][start.col][start.hp] = 1;
	step[start.row][start.col][start.hp] = 0;
	q.push(start);
}

node moveto(node u, int dire)
{//最开始的问题出在没有给u,v生命值
	node v;
	v.row = u.row + mover[dire];
	v.col = u.col + movec[dire];//row写为col
	v.hp = u.hp;
	if (garden[v.row][v.col] == 'w')
	{
		v.hp = u.hp - 1;
	}
	return v;
}

bool canmove(node u, int dire)
{
	node v;
	v = moveto(u, dire);
	if (v.row >= 0 && v.row < m && v.col >= 0 && v.col < n && v.hp > 0 && used[v.row][v.col][v.hp] == 0)
	{
		return true;
	}
	return false;
}

int bfs()
{
	while (!q.empty())
	{
		//取出结点u
		node u, v;
		u = q.front();
		q.pop();
		//扩展u
		for (int i = 0; i < 4; i++)
		{
			if (canmove(u, i))
			{
				v = moveto(u, i);
				if (v.row == target.row && v.col == target.col)
				{
					return step[u.row][u.col][u.hp] + 1;
				}
				used[v.row][v.col][v.hp] = 1;
				step[v.row][v.col][v.hp] = step[u.row][u.col][u.hp] + 1;
				q.push(v);
			}
		}
	}
	return -1;
}

int main()
{
	input();
	init(start);
	int answer;
	answer = bfs();
	cout << answer << endl;
}

/*
下面是测试数据
4 4 2
w!ww
**ww
www+
****

6
4 4 2
w!ww
*www
www+
****

-1
*/

经过这两个题目的讲解，相信你对于广搜的理解应该更深刻了吧，模板都是一样的，好玩的广搜题目

下面我来看第二个题目的升级版

noj1653 僵尸又来了

题目描述

由于聪明的佳佳很善于布置花园，所以僵尸没能在天亮之前冲到佳佳家里，这次僵尸又要来佳佳家做客了，佳佳很高兴，因为姑妈送给佳佳的大嘴花派上了用场。你拿到了花园的地图（以二维矩阵的形式表示）以及起点和佳佳家的位置。花园里一个位置有大嘴花，僵尸到达时会被吃掉，同时从起点又会出来一个新的僵尸，如果僵尸到达大嘴花的位置时，前一个僵尸还没有吃完，大嘴花将被吃掉，看看僵尸能否在天亮前到达佳佳家里？能的话，最少花费多少时间。

题目要求及样例

输入：
输入的第一行包含4个整数：m，n，t, p。代表m行n列的地图、大嘴花吃掉僵尸花费的时间t和距离天亮的时间p。m,n都是小于200的正整数，t是小于10的正整数，第2行开始的m行是m行n列的花园地图，其中!代表起点，+表示佳佳家。*代表通路，@代表大嘴花，#表示墙。

输出：
输出僵尸到达佳佳家最少需要花费的时间。如果在天亮之前无法到达，则输出-1。

输入样例：

4 4 5 50

#!##
**##
**#+
***@

输出样例：

-1

#include<iostream>
#include<queue>

using namespace std;


struct node {
	int row;
	int col;
};

node start, target;//记录结点
int m, n, t, p;//大嘴花
char  garden[200][200];//二维数组【花园】
queue<node> q; //结点队列
int used[200][200];
int step[200][200];//和之前一样使用记录步数

int mover[4] = { -1,0,+1,0 };//上左下右
int movec[4] = { 0,-1,0,+1 };

void input()//忘记吃掉第一行的回车
{
	cin >> m >> n >> t >> p;
	cin.get();
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			garden[i][j] = cin.get();
			if (garden[i][j] == '!')
			{
				start.row = i;
				start.col = j;
			}
			if (garden[i][j] == '+')
			{
				target.row = i;
				target.col = j;
			}
		}
		cin.get();
	}
}

void init(node start)
{
	for (int i = 0; i < 200; i++)
	{
		for (int j = 0; j < 200; j++)
		{
			step[i][j] = 10000;
		}
	}
	used[start.row][start.col] = 1;
	step[start.row][start.col] = 0;
	q.push(start);
}

node moveto(node u, int dire)
{
	node v;
	v.row = u.row + mover[dire];
	v.col = u.col + movec[dire];//row写为col
	return v;
}

bool canmove(node u, int dire)
{
	node v;
	v = moveto(u, dire);
	if (v.row >= 0 && v.row < m && v.col >= 0 && v.col < n && garden[v.row][v.col] != '#' && used[v.row][v.col] == 0)
	{
		return true;
	}
	return false;
}

int bfs()
{
	//想法是将结点记录，将时间记录，在时间*2层压入结点
	node temp;
	int tempt = 10000; //初始化
	while (!q.empty())
	{
		//取出结点u
		node u, v;
		u = q.front();
		q.pop();
		//扩展u
		for (int i = 0; i < 4; i++)
		{
			if (canmove(u, i))
			{
				v = moveto(u, i);
				if (garden[v.row][v.col] == '@')
				{
					if (t <= step[u.row][u.col] + 1)
						continue;
					else //到达时间为再来一次
					{
						temp.row = v.row;
						temp.col = v.col;
						tempt = 2 * (step[u.row][u.col] + 1);//不符合广搜,那就不标记
						continue;//继续
					}
				}
				//
				if (step[u.row][u.col] + 1 == tempt)
				{//加上这个结点
					step[temp.row][temp.col] = tempt;
					q.push(temp);
				}
				//
				if (v.row == target.row && v.col == target.col && step[u.row][u.col] + 1 < p)
				{
					return step[u.row][u.col] + 1;
				}
				used[v.row][v.col] = 1;
				if (step[u.row][u.col] + 1 <= step[v.row][v.col])//由于大嘴花影响
				{
					step[v.row][v.col] = step[u.row][u.col] + 1;
				}
				q.push(v);
			}
		}
		//
		if (tempt != 10000 && q.empty())
		{
			step[temp.row][temp.col] = tempt;
			q.push(temp);
		}
	}
	return -1;
}

int main()
{
	input();
	init(start);
	int answer;
	answer = bfs();
	cout << answer << endl;
}

/*

4 4 5 50
#!##
**#+
**@*
**#*
8
*/

可以把两个地方的判断插入放在一起

if((tempt != 10000 && q.empty()) || (step[u.row][u.col] + 1 == tempt))