您现在的位置是：首页 >学无止境 >寒假学习-第五专题-DFS和BFS网站首页学无止境

1.

Description

古老的显示屏是由 N×M个像素（Pixel）点组成的。一个像素点的位置是根据所在行数和列数决定的。例如 P(2,1) 表示第 2 行第 1 列的像素点。那时候，屏幕只能显示黑与白两种颜色，人们用二进制 0 和 1 来表示。0 表示黑色，1 表示白色。当计算机发出一个指令：P(x,y)=1，则屏幕上的第 x行第 y 列的阴极射线管就开始工作，使该像素点显示白色，若 P(x,y)=0，则对应位置的阴极射线管不工作，像素点保持黑色。在某一单位时刻，计算机以 N×M二维 01矩阵的方式发出显示整个屏幕图像的命令。

例如，屏幕是由 3×4的像素点组成，在某单位时刻，计算机发出如下命令：

(000100110110)​000​001​011​110​​

对应屏幕显示应为：

假设放大后，一个格子表示一个像素点。

由于未知的原因，显示黑色的像素点总是受显示白色的像素点的影响——可能是阴极射线管工作的作用。并且，距离越近，影响越大。这里的距离定义如下：

设有像素点 P1(x1,y1) 和像素点 P2(x2,y2)，则它们之间的距离 D(P1,P2)=∣x1−x2∣+∣y1−y2∣

在某一时刻，计算机发出显示命令后，科学家们期望知道，每个像素点和其最近的显示白色的像素点之间的最短距离是多少——科学家们保证屏幕上至少有一个显示白色的像素点。

上面的例子中，像素 P(1,1)与最近的白色像素点之间的距离为 3，而像素 P(3,2) 本身显示白色，所以最短距离为 0。

Input

第一行有两个数字，NN 和 M (1≤N,M≤182)，表示屏幕的规格。

以下 N 行，每行 M 个数字，0 或 1。为计算机发出的显示命令。

Output

输出文件有 N 行，每行 M 个数字，中间用 1 个空格分开。第 i 行第 j 列的数字表示距像素点 P(i,j) 最近的白色像素点的最短距离。

Sample 1

3 4
0001
0011
0110

3 2 1 0
2 1 0 0
1 0 0 1

Hint

• 对于 30% 的数据：N×M≤10000；
• 对于 100%100% 的数据：N×M≤182^2。

思路：对于求最短路径我们一般可以从BFS入手观察题目可以发现用BFS的确可以解决那么下面说明具体如何实现我们先开一个display数组存储显示命令并开一个队列将信号为1的坐标进行入队然后对该队列的点对外扩展一层并给dist数组赋值为其上一层dist+1并用一个临时队列接受扩展的非1的点然后再入原队列知道队列为空当然还有一点读入时注意用字符进行读入后再转化

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 190;
int display[N][N];
int visit[N][N];
int dist[N][N];
int n, m;
queue<pair<int, int>> q;
int dx[5] = {0, 1, 0, -1, 0}, dy[5] = {0, 0, 1, 0, -1};
void bfs()
{
	queue<pair<int, int>> tmp;
	while(!q.empty()){
		pair<int, int> t = q.front();
		q.pop();
		for(int i = 1; i <= 4; i ++){
			if(t.first+dx[i] >= 1 && t.first+dx[i] <= n && t.second+dy[i] >= 1 && t.second+dy[i] <= m && display[t.first+dx[i]][t.second+dy[i]] != 1 && !visit[t.first+dx[i]][t.second+dy[i]]){
				dist[t.first+dx[i]][t.second+dy[i]] = dist[t.first][t.second] + 1;
				tmp.push(pair<int, int>(t.first+dx[i], t.second+dy[i]));
				visit[t.first+dx[i]][t.second+dy[i]] = 1;
			}
		}
	}
	while(!tmp.empty()){
		q.push(tmp.front());
		tmp.pop();
	}
}
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n; i ++){
		scanf("%*c");
		for(int j = 1;j <= m;j ++){
			char ch;
			scanf("%c", &ch);
			display[i][j] = ch - '0';
			if(ch == '1') q.push(pair<int, int>(i, j));
		}
	}
	while(!q.empty()) bfs();
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= m; j ++){
			cout << dist[i][j] << ' ';
		}
		cout << '
';
	}
	return 0;
}

2.

农民 John 以拥有世界上最健康的奶牛为傲。他知道每种饲料中所包含的牛所需的最低的维他命量是多少。请你帮助农夫喂养他的牛，以保持它们的健康，使喂给牛的饲料的种数最少。

给出牛所需的最低的维他命量，输出喂给牛需要哪些种类的饲料，且所需的饲料剂量最少。

维他命量以整数表示，每种饲料最多只能对牛使用一次，数据保证存在解。

Input

第一行一个整数 v，表示需要的维他命的种类数。
第二行 v 个整数，表示牛每天需要的每种维他命的最小量。

第三行一个整数 g，表示可用来喂牛的饲料的种数。
下面 g 行，第 n 行表示编号为 n 饲料包含的各种维他命的量的多少。

Output

输出文件只有一行，包括牛必需的最小的饲料种数 p；后面有 p 个数，表示所选择的饲料编号（按从小到大排列）。

如果有多个解，输出饲料序号最小的（即字典序最小）。

Sample 1

4
100 200 300 400
3
50  50  50  50
200 300 200 300
900 150 389 399

2 1 3

Hint

【数据范围】
对于 100%的数据，1≤v≤25，1≤g≤15。
输入的所有整数在 [1,1000]范围内。

USACO 2.1

翻译来自NOCOW

 思路：显然这是一道dfs的题目由于数据很小我们并不需要剪枝先开一个vtm数组记录牛所需要的各种维他命的量用feed数组记录各种饲料提供的维他命path数组记录答案p记录种类然后dfs传入两个参数一个为当前种类另一个为所选种类数当当前种类大于总数时进行判断是否够若是比较种类数最后输出即可

AC代码：

#include <bits/stdc++.h>
using namespace std;
int v, g, p = 30;
int vtm[30];
int feed[20][30];
int cow[30];
int tmp_path[30];
int path[30];
void dfs(int t, int s)
{
	if(t > g){
		for(int i = 1; i <= v; i ++){
			if(vtm[i] > cow[i]) return;
		}
		if(p > s){
			p = s;
			for(int i = 1; i <= p; i ++) path[i] = tmp_path[i];
		}
		return ;
	}
	else{
		for(int i = 1; i <= v; i ++) cow[i] += feed[t][i];
		tmp_path[s+1] = t;
		dfs(t+1, s + 1);
		tmp_path[s+1] = 0;
		for(int i = 1; i <= v; i ++) cow[i] -= feed[t][i];
		dfs(t+1, s);
	}
}
int main()
{
	cin >> v;
	for(int i = 1; i <= v; i ++) cin >> vtm[i];
	cin >> g;
	for(int i = 1; i <= g; i ++){
		for(int j = 1; j <= v; j ++) cin >> feed[i][j];
	}
	dfs(1, 0);
	cout << p << ' ';
	for(int i = 1; i <= p; i ++) cout << path[i] << ' ';
	return 0;
}

3.

给定一个 n×n 的网格状地图，每个方格 (i,j) 有一个高度 wij。如果两个方格有公共顶点，则它们是相邻的。

定义山峰和山谷如下：

• 均由地图上的一个连通块组成；
• 所有方格高度都相同；
• 周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。

求地图内山峰和山谷的数量。特别地，如果整个地图方格的高度均相同，则整个地图既是一个山谷，也是一个山峰。

输入格式

第一行一个整数 nn（2≤n≤1000），表示地图的大小。

接下来 n 行每行 n个整数表示地图。第 i 行有 nn 个整数 wi1,wi2,…,win(0≤wij≤1 000 000 000)，表示地图第 i 行格子的高度。

输出格式

输出一行两个整数，分别表示山峰和山谷的数量。

样例解释

翻译来自于 LibreOJ。

输入输出样例

输入 #1复制

5
8 8 8 7 7
7 7 8 8 7
7 7 7 7 7
7 8 8 7 8
7 8 8 8 8

输出 #1复制

2 1

输入 #2复制

5
5 7 8 3 1
5 5 7 6 6
6 6 6 2 8
5 7 2 5 8
7 1 0 1 7

输出 #2复制

3 3

 思路：显然这是一道BFS题目我们首先开一个t_map数组存储高度并开一个标记数组visit先全为0然后对t_map进行遍历若！visit[i][j]则进行BFS对八个方向进行拓展可以先开两个dx和dy数组写好各个方向坐标的加减在BFS函数中用flag记录当前地形若拓展的与初始的相同则入队并visit标记不同根据大小关系对flag进行赋值最后根据flag的值进行加减

AC代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, Ridges = 0, Valleys = 0;
int t_map[N][N];
int visit[N][N];
int dx[9] = {0, 1, 1, 0, -1, -1, -1, 0, 1}, dy[9] = {0, 0, 1, 1, 1, 0, -1, -1, -1};
void bfs(int x, int y)
{
	queue<pair<int, int>> q;
	q.push(pair<int, int>(x, y));
	static int tmp_visit[N][N];
	int flag = 0;
	//cout << t_map[x][y] << ' ';
	while(!q.empty()){
		pair<int, int> t = q.front();
		q.pop();
		for(int i = 1;i <= 8; i ++){
			int new_x = t.first+dx[i];
			int new_y = t.second+dy[i];
			if(new_x >= 1 && new_x <= n && new_y >= 1 && new_y <= n ){
				tmp_visit[new_x][new_y] = 1;
				if(t_map[x][y] < t_map[new_x][new_y]){
					if(flag == 0) flag = 1;
					if(flag == 2) flag = 3;
				}
				else if(t_map[x][y] > t_map[new_x][new_y]){
					if(flag == 0) flag = 2;
					if(flag == 1) flag = 3;
				}
				else if(t_map[x][y] == t_map[new_x][new_y] && !visit[new_x][new_y]){
					//cout << t_map[new_x][new_y] << ' ';
					q.push(pair<int, int>(new_x, new_y));
					visit[new_x][new_y] = 1;
				}
			}
		}
	} 
	//cout << '
';
	if(flag == 1) Ridges++;
	if(flag == 2) Valleys++;
	if(flag == 0) Ridges = Valleys = 1;
	return ;
}
int main()
{
	cin >> n;
	int flag = 0; 
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= n; j ++) cin >> t_map[i][j];
	}
	for(int i = 1; i <= n; i ++){
		for(int j = 1; j <= n; j ++){
			if(!visit[i][j]){
				bfs(i, j);
			}
		}
	}
	cout << Valleys << ' ' << Ridges;
	return 0;
}

4.

一个如下的 6×6 的跳棋棋盘，有六个棋子被放置在棋盘上，使得每行、每列有且只有一个，每条对角线（包括两条主对角线的所有平行线）上至多有一个棋子。

上面的布局可以用序列 2 4 6 1 3 5 来描述，第 i个数字表示在第 i行的相应位置有一个棋子，如下：

行号 1 2 3 4 5 6

列号 2 4 6 1 3 5

这只是棋子放置的一个解。请编一个程序找出所有棋子放置的解。
并把它们以上面的序列方法输出，解按字典顺序排列。
请输出前 3 个解。最后一行是解的总个数。

Input

一行一个正整数 nn，表示棋盘是 n×n 大小的。

Output

前三行为前三个解，每个解的两个数字之间用一个空格隔开。第四行只有一个数字，表示解的总数。

Sample 1

6

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

Hint

【数据范围】
对于 100% 的数据，6≤n≤13。

题目翻译来自NOCOW。

USACO Training Section 1.5

思路：很容易可以看出这道题可以用dfs去解决但是直接对坐标进行dfs显然是会超时的我们可以观察到一些特征当棋子落于（x，y）时x这一行都不能再放棋子y这一列也不能还有经过（x，y）这点的两条对角线上也不能放棋子对于x很好可以用一个dx数组来表达x行的状态关键如何去表达这两条对角线观察可以发现在对角线向上的点的坐标x+y为一常数而向下的x-y+n也是一个常数至此我们就可以分别用两个数组来表示对角线的状态了

AC代码：

#include <stdio.h>
int n;
int a[100] = {0};
int b[100] = {0};
int c[100] = {0};
int jf = 0;
int sz[20] = {0};
void dfs(int x){
	if(x > n){
		jf++;
		if(jf <= 3){
			for(int i = 1; i <= n; i ++) printf("%d ", sz[i]);
			putchar('
');
		}
	}
	else{
		for(int i = 1; i <= n; i ++){
			if(a[i] == 0 && b[i+x] == 0 && c[x-i+n]==0){
				sz[x] = i;
				a[i] = 1;
				b[i+x] = 1;
				c[x-i+n] = 1;
				dfs(x+1);
				a[i] = 0;
				b[i+x] = 0 ;
				c[x-i+n] = 0;
			}
		}
		return ;
	}
}
int main()
{
	scanf("%d", &n);
	dfs(1);
	printf("%d", jf);
	return 0;	
} 

学习总结：

深度优先遍历：在树或图中需要遍历所有节点，且更关注深度方向的探索时使用。例如，遍历目录结构，希望尽可能深入到子目录。

广度优先遍历：在需要按层次或距离起始节点的远近顺序访问节点时使用。例如，社交网络中查找距离某个用户特定步数内的所有用户