深度优先搜索DFS
DFS一般使用递归实现
深度优先算法解决背包问题
#define _CRT_SECURE_NO_WARNINGS 1
#include<cstdio>
const int maxn = 30;
int n, V, maxValue = 0;
int w[maxn], c[maxn];
void DFS(int index, int sumW, int sumC)
{
if (index == n)//死胡同
{
if (sumW <= V && sumC >= maxValue)
{
maxValue = sumC;
}
return;
}
//岔道口
DFS(index + 1, sumW, sumC);//不选第index件物品
DFS(index + 1, sumW + w[index], sumC + c[index]);//选第index件物品
}
int main()
{
scanf("%d %d",&n,&V);//物品件数，背包总容量
for (int i = 0; i < n; i++)
{
scanf("%d", &w[i]);
}
for (int i = 0; i < n; i++)
{
scanf("%d",&c[i]);
}
DFS(0,0,0);
printf("%d\n",maxValue);
return 0;
}
背包问题减枝
void DFS(int index, int sumW, int sumC)
{
if (index == n)//死胡同
{
return;
}
//岔道口
DFS(index + 1, sumW, sumC);//不选第index件物品
if (sumW + w[index] <= V)//选index的时候有条件
{
if (sumC + c[index] > maxValue)
maxValue = sumC + c[index];
DFS(index + 1, sumW + w[index], sumC + c[index]);//选第index件物品
}
}
背包问题减枝2.0
void DFS(int index, int sumW, int sumC)
{
if (index == n)//死胡同
{
if (sumC >= maxValue)
{
maxValue = sumC;
}
return;
}
//岔道口
DFS(index + 1, sumW, sumC);//不选第index件物品
if (sumW + w[index] <= V)//选index的时候有条件
{
DFS(index + 1, sumW + w[index], sumC + c[index]);//选第index件物品
}
}
刚刚没找到codeup网址：在这里记录一下
http://codeup.hustoj.com/contest.php
问题 A: 【递归入门】全排列
#include <cstdio>
int n;
bool flag[20]={false};
int ans[20];
void combine(int count)
{
if(count==n)
{
for(int i=0;i<n;i++)
{
printf("%d ",ans[i]);
}
printf("\n");
return ;
}
for(int i=0;i<n;i++)
{
if(flag[i]==false)
{
ans[count]=i+1;
flag[i]=true;
combine(count+1);
flag[i]=false;
}
}
}
int main()
{
while(~scanf("%d",&n))
{
int count=0;
combine(count);
}
return 0;
}
问题 B: 【递归入门】组合的输出
#include <cstdio>
using namespace std;
int n, r;
int ans[26];
bool flag[26] = { false };
void combine(int x, int count)
{
if (count == r)
{
for (int i = 0; i < r; i++)
{
printf("%d ", ans[i]);
}
printf("\n");
return;
}
for (int i = x; i <= n; i++)
{
if (flag[i - 1] == false)
{
ans[count] = i;
flag[i - 1] = true;
combine(i, count + 1);
flag[i - 1] = false;
}
}
}
int main()
{
while (~scanf("%d %d", &n, &r))
{
combine(1, 0);
}
return 0;
}
问题 C: 【递归入门】组合+判断素数
#include <cstdio>
#include <cmath>
using namespace std;
int n,k,count;
int number[25],sum;
bool isPrime(int n)
{
if(n<=1)
return false;
int sqr=(int)sqrt(1.0*n);
for(int i=2;i<=sqr;i++)
{
if(n%i==0)
return false;
}
return true;
}
void combine_judge(int pos,int level)
{
if(level==k)
{
if(isPrime(sum)==true)
{
count++;
}
return;
}
for(int i=pos;i<n;i++)
{
sum+=number[i];
combine_judge(i+1,level+1);
sum-=number[i];
}
}
int main()
{
while(~scanf("%d %d",&n,&k))
{
for(int i=0;i<n;i++)
{
scanf("%lld",&number[i]);
}
count=0;
sum=0;
combine_judge(0,0);
printf("%d",count);
}
return 0;
}
问题 D: 【递归入门】n皇后 问题（原始的8皇后问题）
#include <cstdio>
int n,result[15],count;
void n_queen(int index)
{
if(index==n)
{
for(int i=0;i<n;i++)
{
printf("%d ",result[i]+1);
}
printf("\n");
count++;
return;
}
bool flag[15]={false};
for(int i=0;i<index;i++)
{
flag[result[i]]=true;
int lower_right=i+result[i]-index;
int top_right=-i+result[i]+index;
if(lower_right>=0)
flag[lower_right]=true;
if(top_right<=n-1)
flag[top_right]=true;
}
for(int i=0;i<n;i++)
{
if(flag[i]==false)
{
result[index]=i;
n_queen(index+1);
}
}
}
int main()
{
while(~scanf("%d",&n))
{
count=0;
n_queen(0);
if(count==0)
printf("no solute!\n");
}
return 0;
}
问题 E: 【递归入门】出栈序列统计
#include <cstdio>
int n,count;
void dispose(int num,int pop,int push)
{
if(pop==0&&push==0)
{
count++;
return;
}
if(push>0)
dispose(num+1,pop,push-1);
if(pop>0&&num>0)
dispose(num-1,pop-1,push);
}
int main()
{
while(~scanf("%d",&n))
{
count=0;
dispose(0,n,n);
printf("%d\n",count);
}
return 0;
}
问题 F: 【递归入门】走迷宫
这题好难呀，留着以后填坑叭orz(逃~
广度优先搜索BFS
BFS通常用队列来实现
在n*m矩阵中找 1“块 ”的个数
- 输入
6 7
0 1 1 1 0 0 1
0 0 1 0 0 0 0
0 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 1 0 0
1 1 1 1 0 0 0
- 输出
4
队列真好用
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<queue>
using namespace std;
const int maxn = 100;
int matrix[maxn][maxn];
int inq[maxn][maxn] = { 0 };//表示inq[i][j]有没有被访问过
int n, m;//矩阵有n行m列
int X[4] = { 0,0,1,-1 };//增量数组
int Y[4] = { 1,-1,0,0 };
struct node {
int x;
int y;
}Node;
int judge(int x, int y)//判断坐标（x,y）是否需要访问,x表示行，y表示列
{
if (x < 0 || y < 0 || x >= n || y >= m) return 0;//如果越界，不需要访问
if (inq[x][y] == 1 || matrix[x][y] == 0) return 0; //如果为0或者已经被访问过，不需要访问
return 1;//不然就可以访问
}
void BFS(int x, int y)
{
Node.x = x;
Node.y = y;
queue < node>q;//定义队列
q.push(Node);
inq[x][y] = 1;//!!!注意这个不能忘记，每次push后就记录Inq为1
while (!q.empty())
{
node top = q.front();
q.pop();//将队首元素出队
for (int i = 0; i < 4; i++)
{
int newX = top.x + X[i];
int newY = top.y + Y[i];
if (judge(newX, newY))
{
Node.x = newX;
Node.y = newY;
q.push(Node);
inq[newX][newY] = 1;//表示已经访问过
}
}
}
}
int main()
{
scanf("%d %d",&n,&m);
int ans = 0;
for (int x = 0; x < n; x++)
for (int y = 0; y < m; y++)
{
scanf("%d",&matrix[x][y]);
}
for(int x=0;x<n;x++)
for (int y = 0; y < m; y++)
{
if (matrix[x][y] == 1 && inq[x][y] == 0)
{
ans++;
BFS(x, y);
}
}
printf("%d\n",ans);
return 0;
}
走迷宫
- 输入
5 5
.....
.*.*.
.*S*.
.***.
...T*
2 2 4 3
- 输出
11
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 100;
char maze[maxn][maxn];
int inq[maxn][maxn] = { 0 };//表示inq[i][j]有没有被访问过
int n, m;//矩阵有n行m列
int X[4] = { 0,0,1,-1 };//增量数组
int Y[4] = { 1,-1,0,0 };
struct node {
int x;
int y;
int step;
}S,T,Node;
int judge(int x, int y)//判断坐标（x,y）是否需要访问,x表示行，y表示列
{
if (x < 0 || y < 0 || x >= n || y >= m) return 0;//如果越界，不需要访问
if (inq[x][y] == 1 || maze[x][y] == '*') return 0; //如果为0或者已经被访问过，不需要访问
return 1;//不然就可以访问
}
int BFS()
{
queue < node> q;//定义队列
q.push(S);
inq[S.x][S.y] = 1;//!!!注意这个不能忘记，每次push后就记录Inq为1
while (!q.empty())
{
node top = q.front();
q.pop();//将队首元素出队
if (top.x == T.x && top.y == T.y)
return top.step;
for (int i = 0; i < 4; i++)
{
int newX = top.x + X[i];
int newY = top.y + Y[i];
if (judge(newX, newY))
{
Node.x = newX;
Node.y = newY;
Node.step = top.step + 1;
q.push(Node);
inq[newX][newY] = 1;//表示已经访问过
}
}
}
return -1;//无法到达终点
}
int main()
{
scanf("%d %d",&n,&m);
for (int x = 0; x < n; x++)
{
getchar();//过滤掉换行符
for (int y = 0; y < m; y++)
{
maze[x][y] = getchar();
}
maze[x][m] = '\0';//最后补上换行符
}
scanf("%d %d %d %d",&S.x,&S.y,&T.x,&T.y);
S.step = 0;
printf("%d", BFS());
return 0;
}
需要注意：
1、设置inq数组的含义是节点是否入队，而不是节点被访问
2、queue中的元素只是原来元素的副本，对队列中副本的修改并不会影响原来的元素
一开始我是这样想的：
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<queue>
//!!这题注意所有做过的点都可以再走一遍，所以不需要判断重复，要根据什么来判断有没有走完呢，到A最少需要8步，走完8步也说明一定可以到达A，只要判断level是否等于8就可以了。
using namespace std;
char matrix[8][8];
char matrix1[8][8];//matrix的替补
int inq[8][8] = { 0 };//表示inq[i][j]有没有进入队列
int X[9] = { 0,0,0,1,-1,1,-1,1,-1 };//增量数组
int Y[9] = { 0,1,-1,0,0,-1,1,1,-1 };//注意也可以选择不走路
struct node {
int x;
int y;
}S,T,Node;
int level;
void change1()
{
for (int i = 7; i >= 0; i--)
{
for (int j = 0; j < 8; j++)
{
matrix1[i][j] = matrix[i][j];
}
}
for (int i = 7; i >= 0; i--)
{
for (int j = 0; j < 8; j++)
{
matrix1[i][j] = matrix1[i - 1][j];
}
}
matrix1[1][7] = '.';
for (int j = 0; j < 7; j++)
matrix1[0][j] = '.';
matrix1[0][7] = 'A';
}
int judge(int x, int y)//判断坐标（x,y）是否可以入队,x表示行，y表示列
{
if (x < 0 || y < 0 || x >= 8 || y >= 8) return 0;//如果越界，不再入队
if ( matrix[x][y] == 'S') return 0; //如果为石头.不再入队
change1();
if (matrix1[x][y] == 'S') return 0;//如果下一步走过去之后为石头
return 1;//不然就可以访问
}
void change()
{
for (int i = 7; i >= 0; i--)
{
for (int j = 0; j < 8; j++)
{
matrix[i][j] = matrix[i - 1][j];
}
}
matrix[1][7] = '.';
for (int j = 0; j < 7; j++)
matrix[0][j] = '.';
matrix[0][7] = 'A';
}
int BFS()
{
queue < node> q;//定义队列
q.push(S);
level = 0;
while (!q.empty())
{
node top = q.front();
q.pop();//将队首元素出队
for (int i = 0; i < 9; i++)
{
int newX = top.x + X[i];
int newY = top.y + Y[i];
if (judge(newX, newY))//如果可以入队
{
level++;
//printf("%c:",matrix[newX][newY]);
//printf("(%d,%d)入队了,level=%d\n", newX, newY, level);
Node.x = newX;
Node.y = newY;
if (level >= 8 || (Node.x == 0 && Node.y == 7))
return 1;//表示可以到达
q.push(Node);
}
}
change();
}
return 0;//无法到达终点
}
int main()
{
int n;
scanf("%d",&n);
int i;
for (i = 1; i <= n; i++)
{
for (int x = 0; x < 8; x++)
{
getchar();//过滤掉换行符
for (int y = 0; y < 8; y++)
{
matrix[x][y] = getchar();
}
matrix[x][8] = '\0';//最后补上换行符
}
S.x = 7, S.y = 0;//左下角方格，起点
T.x = 0, T.y = 7;//右上角方格，终点
if (BFS())
{
printf("Case #%d: Yes\n",i);
}
else
{
printf("Case #%d: No\n", i);
}
getchar();//过滤换行符
}
return 0;
}
但是上面这个代码总是显示错误
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<queue>
//!!这题注意所有做过的点都可以再走一遍，所以不需要判断重复，要根据什么来判断有没有走完呢，到A最少需要8步，走完8步也说明一定可以到达A，只要判断level是否等于8就可以了。
using namespace std;
char matrix[8][8];
int inq[8][8] = { 0 };//表示inq[i][j]有没有进入队列
int dir[9][2] = { {0,1},{0,-1},{1,0},{-1,0},{1,1},{-1,-1},{1,-1},{-1,1},{0,0} };//方向向量
struct node {
int x,y;//坐标
int step;
}S;
int sx, sy, ex, ey;
node now, nex;//定义两个状态，当前状态和下一个状态
int judge(int x, int y)//判断坐标（x,y）是否可以入队,x表示行，y表示列
{
if (x < 0 || y < 0 || x >= 8 || y >= 8) return 0;//如果越界，不再入队
if (matrix[x][y] == 'S') return 0; //如果为石头.不再入队
return 1;//不然就可以访问
}
void change()//落石
{
for (int i = 7; i >= 0; i--)
for (int j = 7; j >= 0; j--)
if (matrix[i][j] == 'S')
{
matrix[i][j] = '.';
if (i <= 6)
matrix[i + 1][j] = 'S';
}
}
void BFS(int c)
{
int flag = 0;
queue < node> q;//定义队列
S.x = sx,S.y = sy, S.step = 0;
q.push(S);
int level = 0;
while (!q.empty())
{
now = q.front();
if (now.step != level)
{
change();
level = now.step;
}
if (matrix[now.x][now.y] == 'S')
{
q.pop();
continue;
}
if (now.step == 8)
{
flag = 1;
break;
}
q.pop();
for (int i = 0; i < 9; i++)
{
if (judge(now.x + dir[i][0], now.y + dir[i][1]) == 1)
{
nex.x = now.x + dir[i][0];
nex.y = now.y + dir[i][1];
nex.step = now.step + 1;
q.push(nex);
}
}
}
if (flag == 0)
printf("Case #%d: No\n", c);
else
printf("Case #%d: Yes\n", c);
}
int main()
{
int n;
scanf("%d",&n);
int i;
for (i = 1; i <= n; i++)
{
for (int x = 0; x < 8; x++)
{
scanf("%s",matrix[x]);
}
for (int x = 0; x < 8; x++)
{
for (int y = 0; y < 8; y++)
{
if (matrix[x][y] == 'U')
{
sx = x, sy = y;//左下角方格，起点
}
if (matrix[x][y] == 'A')
{
ex = x, ey = y;//右上角方格，终点
}
}
}
BFS(i);
}
return 0;
}
这个代码是正确的
改正的代码如下：不得不说bfs的思想很有趣，step==8的判断大大缩短了时间，并且在代码里没有直接判断下一步可不可以走，而是先做一个基本的判断（下标不越界就可以了），在走到是S的坐标时，直接跳过continue,这样就不用每次都要算change1()，导致超时
#define _CRT_SECURE_NO_WARNINGS 1
#include <cstdio>
#include<cstring>
#include<queue>
//!!这题注意所有做过的点都可以再走一遍，所以不需要判断重复，要根据什么来判断有没有走完呢，到A最少需要8步，走完8步也说明一定可以到达A，只要判断step是否等于8就可以了。
using namespace std;
char matrix[8][8];
char matrix1[8][8];//matrix的替补
int inq[8][8] = { 0 };//表示inq[i][j]有没有进入队列
int X[9] = { 0,0,0,1,-1,1,-1,1,-1 };//增量数组
int Y[9] = { 0,1,-1,0,0,-1,1,1,-1 };//注意也可以选择不走路
struct node {
int x;
int y;
int step;
}S, T, now,nex;
int level;
int judge(int x, int y)//判断坐标（x,y）是否可以入队,x表示行，y表示列
{
if (x < 0 || y < 0 || x >= 8 || y >= 8) return 0;//如果越界，不再入队
if (matrix[x][y] == 'S') return 0; //如果为石头.不再入队
return 1;//不然就可以访问
}
void change()
{
for (int i = 7; i >= 0; i--)
{
for (int j = 0; j < 8; j++)
{
matrix[i][j] = matrix[i - 1][j];
}
}
matrix[1][7] = '.';
for (int j = 0; j < 7; j++)
matrix[0][j] = '.';
matrix[0][7] = 'A';
}
void BFS(int c)
{
int flag = 0;
queue < node> q;//定义队列
S.step = 0;
q.push(S);
level = 0;
while (!q.empty())
{
node now = q.front();
if (now.step != level)
{
change();//注意并不是时刻要change，只在一层遍历完后才change
level = now.step;
}
if (matrix[now.x][now.y] == 'S')//在这里判断如果是S,那么不需要直接判断下一个点就好了
{
q.pop();
continue;
}
if (now.step == 8)
{
flag = 1;
break;
}
q.pop();
for (int i = 0; i < 9; i++)
{
int newX = now.x + X[i];
int newY = now.y + Y[i];
if (judge(newX, newY))//如果可以入队
{
nex.x = newX;
nex.y = newY;
nex.step = now.step+1;
q.push(nex);
}
}
}
if (flag == 0)
printf("Case #%d: No\n", c);
else
printf("Case #%d: Yes\n", c);
}
int main()
{
int n;
scanf("%d", &n);
int i;
for (i = 1; i <= n; i++)
{
for (int x = 0; x < 8; x++)
{
scanf("%s", matrix[x]);
}
for (int x = 0; x < 8; x++)
{
for (int y = 0; y < 8; y++)
{
if (matrix[x][y] == 'U')
{
S.x = x, S.y = y;//左下角方格，起点
}
if (matrix[x][y] == 'A')
{
T.x = x, T.y = y;//右上角方格，终点
}
}
}
BFS(i);
}
return 0;
}
问题 C: 【宽搜入门】8数码难题
大神的分析帖：
https://blog.csdn.net/u012283461/article/details/79078653
因为BFS缓了好几天orz,我决定满满把这些题目和题解看了，目前就先这样叭