啊哈算法(4)—万能的搜索
深度优先搜索DFS
深度优先搜索的关键在于解决“当下该如何做”。至于下一步怎么做与当下该如何做是一样的。深度优先搜索的基本模型:
void dfs(int step)
{
判断边界
尝试每一种可能for(i=1;i<=n;++i)
继续下一步dfs(step+1);
}
例1:求1到n的全排列,n为1~9之间任意一个数。
//求1到n的全排列 想相有n个盒子往里面放牌
#include<iostream>
using namespace std;
int a[10], book[10], n;
void dfs(int step) //站在第step个盒子前面
{
if (step == n+1) //边界条件 到n+1时说明前面都已经放好
{
for (int i = 1; i <= n; ++i)
{
cout << a[i] << " " ;
}
cout << endl;
}
else
{
for (int i = 1; i <= n; ++i)
{
if (book[i] == 0) //对每一种还没有尝试的进行尝试 为0的时候表示第i种还没有进行尝试
{
book[i] = 1;
a[step] = i;
dfs(step + 1);
book[i] = 0; //尝试完之后要收回
}
}
}
}
int main()
{
cin >> n;//n位于1到9之间
dfs(1);//现在站在第1个前面
getchar();
}
例2:有1到9几个号码牌,将其填入括号中,使得()()()+()()()=()()()。
其实就是对其求个全排列,并且判断一下a[1]*100+a[2]*10+a[3]+a[4]*100+a[5]*10+a[6]=a[7]*100+a[8]*10+a[9]是否满足,不在列举出代码。
例3:解救小哈,输入几行数,第一行两个数n,m。接下来的n行m列为迷宫,其中0表示可以走的地方,1表示障碍物。最后一行4个数,前两个表示迷宫的入口的x和y的坐标。后两个为小哈的位置。求出最短的步数。
#include<iostream>
#define INT_MAX 0x7fffffff;
using namespace std;
int a[51][51], book[51][51], min = INT_MAX;
int n, m, p, q;
void dfs(int x, int y, int step)
{
int next[4][2] = { { 0,1 },//向右走
{ 1,0 },//向下走
{ 0,-1 },//向左走
{ -1,0 } };//向上走
if (x == p&&y == q)
{
if (step < min)
min = step;
}
else
{
for (int k = 0; k <= 3; ++k) //枚举四种走法
{
int tx = x + next[k][0];
int ty = y + next[k][1];
if (tx<1 || tx>n || ty<1 || ty>m) //判断是否在迷宫范围内
continue;
if (a[tx][ty] == 0 && book[tx][ty] == 0) //判断是否为障碍物或者已经走过
{
book[tx][ty] = 1;
dfs(tx, ty, step + 1);
book[tx][ty] = 0;
}
}
}
}
int main()
{
cin >> n >> m;
int startx, starty;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
cin >> startx >> starty;
//从起点开始搜索 标记为已经走过
book[startx][starty] = 1;
dfs(startx, starty, 0);
cout << min << endl;
}
广度优先搜索BFS
BFS是一种层层递进的搜索方式,通常通过队列来完成,队列中存放的节点层次不超过一。
例1:与上面一个例子相同,不过这里将会采用广度优先搜索的方法完成,这里使用一个数组来模拟一个队列。
#include<iostream>
#define INT_MAX 0x7fffffff;
using namespace std;
struct note
{
int x; //横坐标
int y; //纵坐标
int f; //父亲在队列中的编号,用于输出路径
int s; //步数
};
int main()
{
int a[51][51], book[51][51];
struct note que[2501];// 地图大小为50*50,因此队列中的元素不会超过2500个
int n, m, p, q;
cin >> n >> m;
int startx, starty;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
cin >> startx >> starty>>p>>q;
int next[4][2] = { { 0,1 },//向右走
{ 1,0 },//向下走
{ 0,-1 },//向左走
{ -1,0 } };//向上走
//队列初始化
int head = 1,tail=1; //队列的头和尾后指针
que[head].x = startx;
que[head].y = starty;
que[head].f = 0;
que[head].s = 0;
tail++;
//从起点开始搜索 标记为已经走过
book[startx][starty] = 1;
int flag = 0;//标记是否到达目标地。
while (head < tail) //head和tail范围内表示队列的元素,即队列不为空的时候
{
for (int k = 0; k <= 3; ++k) //枚举四种走法
{
int tx = que[head].x + next[k][0];
int ty = que[head].y + next[k][1];
if (tx<1 || tx>n || ty<1 || ty>m) //判断是否在迷宫范围内
continue;
if (a[tx][ty] == 0 && book[tx][ty] == 0)
{
book[tx][ty] = 1; //不用还原,不同于DFS每个点进入一次队列
//将新的点插入队列中
que[tail].x = tx;
que[tail].y = ty;
que[tail].f = head;//这个节点是head扩展出来的
que[tail].s = que[head].s + 1;//这里的步数类似于层数,队列中元素层数不超过1
tail++;
}
if (tx == p&&ty == q)
{
flag = 1;
break;
}
}
if (flag == 1)
break;
head++;//相当于出队操作
}
cout << que[tail - 1].s << endl;//此时即为最小步长 可以通过note.f来打印出路径
}
DFS BFS实例
例1:解救炸弹人,输入一个n 行 m列的地图其中#表示城墙,G表示敌人,.表示空地,试问在何处安放炸弹可以炸死最多的敌人,一个炸弹可以炸死一行一列的敌人(遇到城墙不可以越过)。
如下输入实例:
13 13 3 3 //地图大小以及起始位置
#############
#GG.GGG#GGG.#
###.#G#G#G#G#
#.......#..G#
#G#.###.#G#G#
#GG.GGG.#.GG#
#G#.#G#.#.#.#
##G...G.....#
#G#.#G###.#G#
#...G#GGG.GG#
#G#.#G#G#.#G#
#GG.GGG#G.GG#
#############
解法1:采用BFS判断,可以到达的空地,并且统计每个空地上安放炸弹时可以炸死的敌人数目,代码如下:
#include<iostream>
using namespace std;
struct note
{
int x;
int y;
};
char a[20][20]; //用来存储地图
int getnum(int x, int y) //统计可以炸毁多少个敌人
{
int i, j, sum = 0;
//向右统计
i = x, j = y;
while (a[i][j]!='#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
j++;
}
//向左统计
i = x, j = y;
while (a[i][j] != '#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
j--;
}
//向下统计
i = x, j = y;
while (a[i][j] != '#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
i++;
}
//向上统计
i = x, j = y;
while (a[i][j] != '#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
i--;
}
return sum;
}
int main()
{
struct note que[401];// 假设地图大小不超过20*20,扩展队列不会超过401
int head, tail;//队列的头和尾
int book[20][20] = {0};//用来标记当前点是否走过
int next[4][2] = { {0,1},{0,-1},{1,0},{-1,0} };//可以走的四个方向
int sum, max = 0, mx, my;//记录最大可以炸死的敌人个数,和放置炸弹的坐标
int n, m, startx, starty; //地图的大小行数和列数 以及起使位置
cin >> n >> m >> startx >> starty;
for (int i = 0; i <= n - 1; ++i) //存入地图
for (int j = 0; j <= m - 1; ++j)
cin >> a[i][j];
//起点入队
head = 1, tail = 1;
que[head].x = startx;
que[head].y = starty;
tail++;
book[startx][starty] = 1;
max = getnum(startx, starty);
mx = startx, my = starty;
//遍历整个图
while (head<tail)
{
int tx, ty;
for (int k = 0; k < 4; ++k) //枚举四个方向
{
tx=que[head].x + next[k][0];
ty=que[head].y + next[k][1];
if (tx<0 || tx>n - 1 || ty<0 || ty>m - 1) //不合法 旧尝试下一种情况
continue;
if (a[tx][ty] == '.'&&book[tx][ty] == 0) //是空地并且没有走过
{
book[tx][ty] = 1;
que[tail].x = tx; //入队
que[tail].y = ty;
tail++;
sum = getnum(tx, ty);//统计当前点放置炸弹可以炸死多少敌人
if (sum > max) //更新当前最大值以及放置炸弹的位置
{
max = sum;
mx = tx;
my = ty;
}
}
}
head++;// 出队
}
cout << "将炸弹放置在" << mx << " " << my << "可以消灭" << max << "个敌人";
system("pause");
}
解法2:采用DFS判断每一个点,过程如****意这里遍历到每个点就可以,所以不用回溯)
#include<iostream>
using namespace std;
char a[20][20]; //用来存储地图
int book[20][20];//用来标记当前点是否走过
int sum, max, mx, my;//记录最大可以炸死的敌人个数,和放置炸弹的坐标
int n, m, startx, starty; //地图的大小行数和列数 以及起使位置
int getnum(int x, int y) //统计可以炸毁多少个敌人
{
int i, j, sum = 0;
//向右统计
i = x, j = y;
while (a[i][j] != '#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
j++;
}
//向左统计
i = x, j = y;
while (a[i][j] != '#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
j--;
}
//向下统计
i = x, j = y;
while (a[i][j] != '#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
i++;
}
//向上统计
i = x, j = y;
while (a[i][j] != '#')//不是墙就可以继续
{
if (a[i][j] == 'G')
sum++;
i--;
}
return sum;
}
void dfs(int x, int y)
{
int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
sum = getnum(x, y);//统计当前点放置炸弹可以炸死多少敌人
if (sum > max) //更新当前最大值以及放置炸弹的位置
{
max = sum;
mx = x;
my = y;
}
for (int k = 0; k < 4; ++k) //枚举四个方向
{
int tx = x + next[k][0];
int ty = y + next[k][1];
if (tx<0 || tx>n - 1 || ty<0 || ty>m - 1) //不合法 旧尝试下一种情况
continue;
if (a[tx][ty] == '.'&&book[tx][ty] == 0) //是空地并且没有走过
{
book[tx][ty] = 1; //只是判断每个点,不用回溯
dfs(tx, ty);
}
}
}
int main()
{
cin >> n >> m >> startx >> starty;
for (int i = 0; i <= n - 1; ++i) //存入地图
for (int j = 0; j <= m - 1; ++j)
cin >> a[i][j];
dfs(startx, starty);
cout << "将炸弹放置在" << mx << " " << my << "可以消灭" << max << "个敌人";
system("pause");
}
例2:宝岛探险,给出一幅n行m列的地图,其中0表示海洋,1到9表示陆地,求独立的岛屿个数。(即是求一个图中,独立的子图的个数)
输入示例:
10 10
1 2 1 0 0 0 0 0 2 3
3 0 2 0 1 2 1 0 1 2
4 0 1 0 1 2 3 2 0 1
3 2 0 0 0 1 2 4 0 0
0 0 0 0 0 0 1 5 3 0
0 1 2 1 0 1 5 4 3 0
0 1 2 3 1 3 6 2 1 0
0 0 3 4 8 9 7 5 0 0
0 0 0 3 7 8 6 0 1 2
0 0 0 0 0 0 0 0 1 0
解法1:BFS解法,对岛屿进行着色,(觉得采用DFS比较好)
#include<iostream>
using namespace std;
int a[51][51]; //存储地图
int book[51][51]; //标记是否走过
int n, m; //地图大小
struct note
{
int x;
int y;
};
int main()
{
int color = 0;//对每个岛屿着色
struct note que[2501]; //扩展队列 地图大小为50*50 扩展队列不会超过2501
int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
cin >> n >> m;
for (int i = 1; i <= n; ++i) //读入地图
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
for (int i = 1; i <= n; ++i) //对每一个非0的点进行BFS
{
for (int j = 1; j <= m; ++j)
{
if (a[i][j] > 0)
{
--color;
a[i][j] = color; //进行染色
int head = 1, tail = 1; //入队
que[head].x = i;
que[head].y = j;
tail++;
book[i][j] = 1;
while (head<tail)
{
for (int k = 0; k < 4; ++k) //遍历四个方向
{
int tx = que[head].x + next[k][0];
int ty = que[head].y + next[k][1];
if (tx<1 || tx>n || ty<1 || ty>m) //判断边界是否满足
continue;
if (a[tx][ty] > 0 && book[tx][ty] == 0)
{
a[tx][ty] = color; //入队前进行染色
que[tail].x = tx;
que[tail].y = ty;
tail++;
book[tx][ty] = 1;
}
}
head++;
}
}
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cout << a[i][j] << " ";
}
cout << endl;
}
cout << "有" << -color << "个小岛";
system("pause");
}
解法二:采用DFS,进行着色 (相比于BFS容易实现点)
#include<iostream>
using namespace std;
int a[51][51]; //存储地图
int book[51][51]; //标记是否走过
int n, m; //地图大小
int color;
void dfs(int x, int y)
{
int next[4][2] = { { 0,1 },{ 0,-1 },{ 1,0 },{ -1,0 } };//可以走的四个方向
a[x][y] = color;
for (int k = 0; k < 4; ++k) //遍历四个方向
{
int tx = x + next[k][0];
int ty = y + next[k][1];
if (tx<1 || tx>n || ty<1 || ty>m) //判断边界是否满足
continue;
if (a[tx][ty] > 0 && book[tx][ty] == 0)
{
book[tx][ty] = 1;
dfs(tx, ty); //不用回溯
}
}
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i) //读入地图
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
for (int i = 1; i <= n; ++i) //对每一个非0的点进行BFS
{
for (int j = 1; j <= m; ++j)
{
if (a[i][j] > 0)
{
color--;
dfs(i, j);
}
}
}
for (int i = 1; i <= n; ++i)
{
for (int j = 1; j <= m; ++j)
{
cout << a[i][j] << " ";
}
cout << endl;
}
cout << "有" << -color << "个小岛";
system("pause");
}
例3:水管工游戏:(题目参考《啊哈算法》。。)
#include<iostream>
using namespace std;
int a[51][51];
int book[51][51], n, m,flag;
struct note
{
int x;
int y;
}s[100];
int top = 0;
void dfs(int x,int y,int front) //front 代表进水口方向
{
if (x == n&&y == m + 1)
{
flag = 1;
for (int i = 1; i <= top; ++i)
cout << "("<<s[i].x << "," << s[i].y << ")" << " ";
cout << endl;
return;
}
if (x<1 || x>n || y<1 || y>m)
return;
if (book[x][y] == 1)
return;
book[x][y] = 1;
top++;
s[top].x = x;
s[top].y = y;
if (a[x][y] >= 5 && a[x][y] <= 6) //为直管的情况
{
if (front == 1) //进水口在左边
{
dfs(x, y + 1, 1);
}
if (front == 2) //进水口在上边
{
dfs(x + 1, y, 2);
}
if (front == 3) //进水口在右边
{
dfs(x, y-1, 3);
}
if (front == 4) //进水口在下边边
{
dfs(x -1, y, 4);
}
}
if (a[x][y] >= 1 && a[x][y] <= 4) //为弯管的时候
{
if (front == 1) //进水口在左边
{
dfs(x+1, y , 2);
dfs(x-1 , y, 4);
}
if (front == 2) //进水口在上边
{
dfs(x , y + 1, 1);
dfs(x, y - 1, 3);
}
if (front == 3) //进水口在右边
{
dfs(x+1, y , 2);
dfs(x - 1, y, 4);
}
if (front == 4) //进水口在下边
{
dfs(x, y + 1, 1);
dfs(x, y - 1, 3);
}
}
book[x][y] = 0; //取消标记
top--; //将当前尝试坐标出栈
return;
}
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++i)
for (int j = 1; j <= m; ++j)
cin >> a[i][j];
dfs(1, 1, 1);
if (flag == 0)
cout << "impossible" << endl;
system("pause");
}