ACM寒假第五讲

一、自然数的拆分问题

设计思路

题目要求对于任何一个大于 1的自然数 n，总可以拆分成若干个小于 n的自然数之和。现在给你一个自然数 n，要求你求出 n的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列，其中字典序小的序列需要优先输出。这边考虑用回溯的方法做：当某种拆分可行之后进行回退，并存储在一个数组中，逐步进行分解。但是当回溯时遇到了一点问题：程序会把自然数n也输出，因为他也是回溯进程中的一项，这边的的解决方案是设置限制条件，因为自然数n本身只有一个，限制size即可。

设计代码

#include <iostream>
#include <vector>
using namespace std;

void btrack(int n, int start, vector<int> &current) {//回溯进程
	if (n == 0) {
		for (int i = 0; i < current.size() ; i++) {
			if (current.size() > 1) {//限制条件
				if (i > 0)
					cout << "+";
				cout << current[i];
			}
		}
		cout << endl;
		return;
	}

	for (int i = start; i <= n; i++) {
		current.push_back(i);
		btrack(n - i, i, current);//回退
		current.pop_back();//本步做完进行弹出
	}
}

int main() {
	int n;
	cin >> n;
	vector<int> current;
	btrack(n, 1, current);//从1开始进程
	return 0;
}

二、填涂颜色

设计思路

题目要求设计一个程序，将方阵中符合“闭合圈”规律的数字0改为数字2。对于本体，刚开始思考是使用深度优先搜索，即dfs，但是在搜索中发现一个问题：不能及时判断是否处于闭合圈内。于是进行思路转换：先把方阵都置为2，再将1进行输入，最后判断闭合圈外的数字2，置为0即可。这样做的优点是闭合圈外好判断，即若上下左右有一个为数字2，就证明本身一定是在闭合圈外的（因为若数字为1说明在闭合圈边界，此时跳过即可），置为0即可。

设计代码

#include <bits/stdc++.h>
using namespace std;
int a[31][31], n;

int dx[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};//方向数组，代表上下左右。
void dfc(int x, int y) {
	a[x][y] = 0;//置零
	for (int i = 0; i < 4; i++) {
		int ux = x + dx[i][0], uy = y + dx[i][1];//上下左右判断
		if (ux >= 0 && ux <= n + 1 && uy >= 0 && uy <= n + 1 && a[ux][uy] == 2) {//判断是否超出边界以及是否在闭合圈外
			dfc(ux, uy);
		}
	}
}
int main() {
	for (int i = 0; i < 31; i++)
		for (int j = 0; j < 31; j++)
			a[i][j] = 2;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int x;
			cin >> x;
			if (x == 1)
				a[i][j] = 1;
		}
	}
	dfc(0, 0);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cout << a[i][j] << " ";
		}
		cout << endl;
	}
	return 0;
}

三、显示图像

设计思路

题目需要计算每个像素点距离其最近的白色像素点的距离，注意：本身为白色像素点的话，距离为0。与上一题类似，也是采用深度优先搜索。但是要注意，本次的路径数组还要加上[0]方向表示自身，以及要需要标记数组表示已经搜索过（为什么上一题不用？——因为上一题的数字就代表标记数组了，2代表没搜索过，1代表边界，以此类推）

设计代码

#include <bits/stdc++.h>
using namespace std;

char a[200][200] = { 0 };
bool isfind[200][200] = {false};//标记函数
int ans[200][200] = { 0 };
int main() {
	int n, m;
	vector<pair<int, int>>f;
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			if (a[i][j] != '0') {//如果是白色的
				isfind[i][j] = true;//表示已搜索过
				f.push_back(make_pair(i, j));//置入
			}
		}
	}
	int dx[5] = { 0, 1, -1, 0, 0 };
	int dy[5] = { 0, 0, 0, 1, -1 };
	for (int i = 0; i < f.size(); i++)
		for (int j = 1; j <= 4; j++) {
			int tx = f[i].first + dx[j];
			int ty = f[i].second + dy[j];
			if (tx >= 1 && tx <= n && ty >= 1 && ty <= m  && isfind[tx][ty] == false) {//判断方向，注意，包括本身
				ans[tx][ty] = ans[f[i].first][f[i].second] + 1;//表示下一个比之前的要多一步，所以要加一
				isfind[tx][ty] = true;
				f.push_back(make_pair(tx, ty));//继续置入，深度搜索
			}
		}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++)
			cout << ans[i][j] << " ";
		cout << endl;
	}
	return 0;
}

四、健康的荷斯坦奶牛

设计思路

这个题目给定v中奶牛需要的维他命，并且给了g中饲料，要求我们判断能够维持奶牛所需维他命的最少的饲料的种类，同第一题类似，这边也是采用回溯的方法。当某一种方法满足后，我们进而思考去掉某一周饲料可不可以满足，并逐步进行递归排查即可。

设计代码

#include <bits/stdc++.h>
using namespace std;
int ans[1000], v[1000], siliao[1000][1000], a[1000];
int vt, g, minn = 100000000;

bool isfull(int x) {//判断是否满足要求
	for (int i = 1; i <= vt; i++) {
		int sum = 0;
		for (int j = 1; j <= x; j++)
			sum += siliao[a[j]][i];
		if (sum < v[i])//某一类不满足则false
			return false;
	}
	return true;
}

void find(int t, int s) {//寻找匹配方案
	if (t > g) {
		if (isfull(s)) {//满足条件
			if (s < minn) {
				minn = s;//置换答案
				for (int i = 1; i <= minn; i++) {
					ans[i] = a[i];//同步替换
				}
			}
		}
		return;
	}
	a[s + 1] = t;//进行标记
	find(t + 1, s + 1);//如果采用某种饲料
	a[s + 1] = 0;//回溯
	find(t + 1, s);//如果不采用某种饲料
}

int main() {
	cin >> vt;
	for (int i = 1; i <= vt; i++)
		cin >> v[i];
	cin >> g;
	for (int i = 1; i <= g; i++) {
		for (int j = 1; j <= vt; j++)
			cin >> siliao[i][j];
	}
	find(1, 0);
	cout << minn << ' ';
	for (int i = 1; i <= minn; i++)
		cout << ans[i] << ' ';
	return 0;
}

五、学习总结

在这次学习中，初步认识了深度优先搜索和广度优先搜索，并稍微了解了他们在代码中的运用，关键在于能否抓住条件合理使用递归方案进行求解，以及对应的标记判断方案，才能完成任务。