2021-10-17

学习《挑战程序设计竞赛》
2.1 最基础穷竭搜索
基础：递归函数、栈、队列
深度优先搜索：
部分和问题
给定整数a1、a2、…an，判断是否可以从中选出若干数，使它们的和恰好为K。

#include
#define MAX 100000
using namespace std;
int a[MAX]={0};
int n=0,k=0;

bool dfs(int i,int sum)
{
	if(i==n)
	{
		return sum==k;
	}
	if(dfs(i+1,sum))
	{
		cout<<"不加入元素"<>n>>k;
	for(int i=0;i>a[i];
	}
	solve();
	return 0;
}

八联通积水问题
有一个大小为N × M的园子，雨后积起了水。八连通的积水被认为是连接在一起的。请求出园子里总共有多少水洼？
样例输入：
10 12
w…ww.
.www…www
…ww…ww.
…ww.
…w…
…w…w…
.w.w…ww.
w.w.w…w.
.w.w…w.
…w…w.

#include
#define MAX 10000
using namespace std;
char field[MAX][MAX];
int N,M;

void dfs(int x,int y)
{
	field[x][y]='.';
	
	for(int i=-1;i<=1;i++)
	{
		for(int j=-1;j<=1;j++)
		{
			int dx=x+i,dy=y+j;
			if(dx>=0&&dx=0&&dy>N>>M;
	for(int i=0;i>field[i][j];
		}
	}
	solve();
	return 0;
}

宽度优先搜索
迷宫最短路径
给定一个大小为N * M 的迷宫。迷宫由通道和墙壁组成，每一步可以向邻接的上下左右四格的通道移动。请求出从起点到终点所需的最小步数。请注意，本题假定从起点一定可以移动到终点 。
限制条件： N ， M<=100 。（ # . S G 分别代表 墙壁、通道、起点和终点。）
样例：
10 10
#s######.#
…#…#
.#.##.##.#
.#…
##.##.####
…#…#
.#######.#
…#…
.####.###.
…#…G#

#include 
#include
#define MAX 10000
const int INF=10000000;
using namespace std;
typedef pair p;
int d[MAX][MAX];
char maze[MAX][MAX];
int N,M;
int sx,sy;
int gx,gy;
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};

int dfs()
{
	queue
 que;
	que.push(p(sx,sy));
	for(int i=0;i=0&&nx=0&&ny>N;
	cin>>M;
	for(int i=0;i>maze[i][j];
			if(maze[i][j]=='S')
			{
				sx=i;
				sy=j;
			}
			if(maze[i][j]=='G')
			{
				gx=i;
				gy=j;
			}
		}
	}
	solve();
	return 0;
}

运用了队列来实现

next_permutation函数
可以对于序列的每一个排列顺序进行 *** 作，以打印该顺序为例：

#include
#include
using namespace std;
int perm[10000]={0};

void solve(int n)
{
	for(int i=0;i 
例：perm最初被赋值为{1，2，3}
 结果为
 
					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/3970118.html