搜索
深度优先搜索
问题：输入一个数n，输出1~n的全排列。 将此问题形象化，举个例子，假如有编号为1，2，3的3张扑克牌和编号为1，2，3的3个盒子。现在需要把三张扑克牌放入三个盒子里有多少钟不同的方法？
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int n, a[100], book[100];
void dfs(int step)//step表示现在站在第几个盒子面前
{
if (step == n + 1) { //step==n+1那么前n个盒子已经放完扑克牌了
for (int i = 1; i <= n; i++) //输出排列结果
cout << a[i] << " ";
cout << endl;
return; //这里要return 返回之前的一步（最近一次调用dfs的地方
}
//此时站在第step个盒子前应该放哪张牌呢？
//按照1，2，3...n的顺序一一尝试
for (int i = 1; i <= n; i++) {
//判断扑克i是否在手上
if (book[i] == 0) { //book[i]==0表示没放进盒子里在手上
a[step] = i; //将i号扑克放进第step个盒子里
book[i] = 1; //第i号扑克已经不在手上了
//第step个盒子已经放好扑克，接下来需要走到下一个盒子面前
dfs(step + 1); //通过函数的递归调用来实现
book[i] = 0; //这是非常重要的一步回收，将放入的扑克牌回收，才能进行下一次的尝试
}
}
return;
}
int main() {
cin >> n;
dfs(1);
system("pause");
return 0;
}再来理一遍代码思路：首先输入n之后，dfs(1)，从第一个盒子开始尝试。进入for循环，i=1，第一张扑克牌放入第一个盒子里，标记此张扑克牌被使用即book[1]=1;然后dfs(2)，第二个盒子里放入第二张扑克牌，因为book[1]被使用了，接着dfs(3),dfs(4)...dfs(n)，然后dfs(n+1)这时已经放完了全部盒子，可以输出了。输出完结果后return回到最近一次调用dfs的地方然后将book[n]收回，接着for循环结束return回到dfs(n-1),book[n-1]=0了，循环发现book[n]在手里于是把第十张扑克牌放进第九个盒子里，第九张扑克牌放进第个箱子里，输出return,接下来按照刚才的步骤模拟，便会依次形成所有的排列。
深度优先搜索的基本模型：
void dfs(int step)
{
判断边界
尝试每一种可能for(int i = 1; i <= n; i++)
{
继续下一步 dfs(step+)；
}
返回
}问题：有1~9九个数字，个选三个数字不可重复组成三个三位数，使其中两个数相加等于另一个数，并输出。
#include<iostream>
using namespace std;
int a[10],book[10],total=0;
void dfs(int step)
{
int x = a[1] * 100 + a[2] * 10 + a[3], y = a[4] * 100 + a[5] * 10 + a[6], z = a[7] * 100 + a[8] * 10 + a[9];
if (x + y == z&&step==10) {
total++;
cout << x << "+" << y << "=" << z << endl;
return ;
}
for (int i = 1; i <= 9; i++) {
if (book[i] == 0) {
a[step] = i;
book[i] = 1;
dfs(step + 1);
book[i] = 0;
}
}
return;
}
int main() {
dfs(1);
cout << "total=" << total / 2;
//system("pause");
return 0;
}迷宫问题
解救小哈：在一个地图上1为障碍物，0为空地，给出起始坐标和终点，找出从起点到终点的最小步数：
#include<iostream>
using namespace std;
const int INF = 1e7;
int p, q,n,m,min=INF;
int a[55][55], book[55][55];
void dfs(int x, int y,int step)
{
//判断是否到达指定位置
if (x == p && y == q) {
if (step < min) //更新最小步数
min = step;
return; //注意这里的return很重要
}
int next[4][2] = {
{0,1},{1,0},{0,-1},{-1,0}
};
int tx, ty;
for (int k = 0; k <= 3; k++) {
//计算下一个点的坐标
tx = x + next[k][0];
ty = y + next[k][1];
//判断是否越界
if (tx<1 || ty<1 || tx>n || 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; //尝试结束，取消这个点的标记
}
}
return;
}
int main() {
int startx, starty;
cin >> n >> m; //读入迷宫大小,n行m列
//读入迷宫
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
//读入起点和终点坐标：
cin >> startx >> starty >> p >> q;
//从起点开始搜索
book[startx][starty] = 1;//标记起点已在路径中，防止后面重复走
dfs(startx, starty, 0);
cout << min << endl;
system("pause");
return 0;
}层层递进——广度优先搜索
在上面解救小哈的行动中使用了深度优先搜索的方法，让小哼往右走，然后一直尝试下去，直到走不通再回到这里，可以通过函数的递归实现。
另一种方法：通过“一层一层”扩展的方法找到小哈，扩展时每发现一个点就将这个点加入到队列中，直至走到小哈的位置(p,q)为止。
#include<iostream>
using namespace std;
struct note
{
int x;//横坐标
int y;//纵坐标
int f;//父亲在队列中的编号
int s;//步数
};
int main(){
struct note que[2501];//队列扩展大小不会超过的大小根据地图大小而定
int a[51][51] = { 0 };
int book[51][51] = { 0 };
//定义一个用于走的方向数组
int next[4][2] = { {0,1},//向右走
{1,0},//向下走
{0,-1},//向左走
{-1,0} };//向上走
int head = 0, tail = 0;
int n, m, startx, starty, p, q,tx,ty,falg;
cin >> n >> m;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
cin >> startx >> starty >> p >> q;
//队列初始化
head = 1, tail = 1;
//往队列插入迷宫初始坐标
que[tail].x = startx;
que[tail].y = starty;
que[tail].f = 0;
que[tail].s = 0;
tail++;
book[startx][starty] = 1;
falg = 0;//用来标记是否到达目标点，0为未到达，1为到达
//当队列不为空时循环
while (head < tail) {
//枚举四个方向
for (int k = 0; k <= 3; k++) {
//计算下一个点的坐标
tx = que[head].x + next[k][0];
ty = que[head].y + next[k][1];
//判断是否越界
if (tx<1 || ty<1 || tx>n || ty>m)
continue;
//判断是否有障碍物或者已在路径中
if (a[tx][ty] == 0 && book[tx][ty] == 0) {
//把这个点标记走过
//注意宽搜每个点只入队一次，所以和深搜不同，不需要将book数组还原
book[tx][ty] = 1;
//插入新的点到队列中
que[tail].x = tx;
que[tail].y = ty;
que[tail].f = head;//这个点从head点扩展出来的，可用于求路径
que[tail].s = que[head].s + 1;//步数是父亲放入步数加一
tail++;
}
//到达目标点停止扩展，结束循环
if (tx == p && ty == q) {
falg = 1;
break;
}
}
if (falg == 1)
break;
head++;
}
//打印队列中末尾最后一个点
//注意tail是指向队尾的下一个位置，所以这里需要减一
cout << que[tail-1].s << endl;
//system("pause");
return 0;
}炸弹人
题意：题目是走迷宫放炸弹，#代表墙，"."代表空地，G是敌人，问在哪一点空地摆放炸弹消灭的敌人最多，炸弹是按同行同列十字形的方式消除敌人的
#include<iostream>
using namespace std;
struct note
{
int x;//横坐标
int y;//纵坐标
};
char a[20][21];
int getnum(int i, int j)
{
int sum = 0, x, y;
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
x++;
}
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
y++;
}
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
y--;
}
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
x--;
}
return sum;
}
int main() {
struct note que[401];
int head, tail;
int book[20][20] = {0};
int startx, starty, n, m, tx, ty, sum, mx, my, maxn = 0;
int next[4][2] = { {0,1},
{1,0},
{0,-1},
{-1,0} };
cin >> n >> m >> startx >> starty;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
head = 1;
tail = 1;
que[tail].x = startx;
que[tail].y = starty;
tail++;
book[startx][starty] = 1;
maxn = getnum(startx, starty);
mx = startx;
my = starty;
//当队列不为空时循环
while (head < tail) {
for (int k = 0; k <= 3; 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 > maxn) {
maxn = sum;
mx = tx;
my = ty;
}
}
}
head++;
}
cout << "将炸弹放置在" << mx << "," << my << "处，可以消灭" << maxn << "个敌人";
system("pause");
return 0;
}此题也可用深度优先搜索解：
#include<iostream>
using namespace std;
char a[20][21];
int getnum(int i, int j)
{
int sum = 0, x, y;
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
x++;
}
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
y++;
}
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
y--;
}
x = i, y = j;
while (a[x][y] != '#') {
if (a[x][y] == 'G')
sum++;
x--;
}
return sum;
}
int book[20][20] = { 0 };
int startx, starty, n, m, tx, ty, sum, mx, my, maxn = 0;
int Next[4][2] = { {0,1},
{1,0},
{0,-1},
{-1,0} };
void dfs(int x, int y)
{
sum = getnum(x, y);
if (sum > maxn) {
maxn = sum;
mx = x;
my = y;
}
for (int k = 0; k <= 3; k++) {
//尝试下一个点坐标
tx = x + Next[k][0];
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);
}
}
return;
}
int main() {
cin >> n >> m >> startx >> starty;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> a[i][j];
book[startx][starty] = 1;
maxn = getnum(startx, starty);
mx = startx;
my = starty;
dfs(startx, starty);
cout << mx << " " << my << " " << maxn;
system("pause");
return 0;
}宝岛探险
0表示海洋，1~9表示陆地相连接的陆地为同一岛屿，求一点的岛屿面积
广度优先搜索：
#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> note;
int main() {
int a[51][51];
int book[51][51] = { 0 };
queue<note> que;
int sum, maxn = 0, mx, my, n, m, startx, starty, tx, ty;
int next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
cin >> n >> m >> startx >> starty;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
que.push(note(startx, starty));
book[startx][starty] = 1;
sum = 1;
while (!que.empty()) {
for (int k = 0; k < 4; k++) {
tx = que.front().first + next[k][0];
ty = que.front().second + 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;
sum++;
que.push(note(tx, ty));
}
}
que.pop();
}
cout << sum << endl;
//system("pause");
return 0;
}深度优先搜索：
这种方法又叫做着色法：以某个点为源点对其邻近的点进行着色。我们可以将代码稍加改动，将小哼降落的岛都改为-1，表示该岛被小哼玩遍（注释掉部分）
#include<iostream>
using namespace std;
int a[51][51];
int book[51][51] = { 0 };
int n, m, sum;
void dfs(int x, int y)
//void dfs(int x, int y, int color)
{
int Next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int tx, ty;
//int a[x][y]=color;
for (int k = 0; k <= 3; k++) {
tx = x + Next[k][0];
ty = y + Next[k][1];
if (tx<1 || ty<1 || tx>n || ty>m)
continue;
if (a[tx][ty] > 0 && book[tx][ty] == 0) {
sum++;
book[tx][ty] = 1;
dfs(tx, ty);
//dfs(tx, ty, color);
}
}
return;
}
int main() {
int startx, starty;
cin >> n >> m >> startx >> starty;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
cin >> a[i][j];
sum = 1;
book[startx][starty] = 1;
dfs(startx, starty);
//dfs(startx,starty,-1)
//输出染色后地图：
/*
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cout<<a[i][j]<<" ";
}
cout<<endl;
}
*/
cout << sum << endl;
system("pause");
return 0;
}如果想知道这个地图中有多少个独立的小岛又该怎么做呢？
很简单，只需要对地图上的每一个大于0的点都进行一遍深度优先搜索即可，对每个点进行尝试染色。
#include<iostream>
using namespace std;
int a[51][51];
int book[51][51] = { 0 };
int n, m, sum;
void dfs(int x, int y,int color)
{
int Next[4][2] = { {0,1},{1,0},{0,-1},{-1,0} };
int tx, ty;
a[x][y] = color;
for (int k = 0; k <= 3; k++) {
tx = x + Next[k][0];
ty = y + Next[k][1];
if (tx<1 || ty<1 || tx>n || ty>m)
continue;
if (a[tx][ty] > 0 && book[tx][ty] == 0) {
sum++;
book[tx][ty] = 1;
dfs(tx, ty,color);
}
}
return;
}
int main() {
int startx, starty;
int num = 0;
cin >> n >> m;
sum = 1;
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++) {
for (int j = 1; j <= m; j++) {
if (a[i][j] > 0) {
num--;
book[i][j] = 1;
dfs(i, j, num);
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
cout << "有" << -num << "个小岛" << endl;
system("pause");
return 0;
}水管工游戏
#include<iostream>
using namespace std;
int a[51][51], book[51][51] = { 0 }, n, m, falg = 0;
struct note
{
int x;
int y;
}s[100];
int top = 0;
void dfs(int x, int y, int front)
{
if (x == n && y == m + 1){
falg = 1;
for (int i = 1; i <= top; i++)
cout << "(" << s[i].x << "," << s[i].y << ") ";
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 , 4);
dfs(x + 1, y , 2);
}
if (front == 4) {
dfs(x , y + 1, 1);
dfs(x , y - 1, 3);
}
}
book[x][y] = 0;
top--;
return;
}
int main() {
int num = 0;
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 (falg == 0)
cout << "impossible" << endl;
//system("pause");
return 0;
}更新中······