C语言-算法-搜索

深度优先搜索（DFS）

例题

迷宫

题目描述

给定一个 $N\times M$ 方格的迷宫，迷宫里有 $T$ 处障碍，障碍处不可通过。

在迷宫中移动有上下左右四种方式，每次只能移动一个方格。数据保证起点上没有障碍。

给定起点坐标和终点坐标，每个方格最多经过一次，问有多少种从起点坐标到终点坐标的方案。

输入格式

第一行为三个正整数 $N,M,T$，分别表示迷宫的长宽和障碍总数。

第二行为四个正整数 $SX,SY,FX,FY$，$SX,SY$ 代表起点坐标，$FX,FY$ 代表终点坐标。

接下来 $T$ 行，每行两个正整数，表示障碍点的坐标。

输出格式

输出从起点坐标到终点坐标的方案总数。

样例 #1

样例输入 #1

2 2 1
1 1 2 2
1 2

样例输出 #1

1

提示

对于 $100\%$ 的数据，$1\le N,M\le 5$，$1\le T\le 10$，$1\le SX,FX\le n$，$1\le SY,FY\le m$。

题解

1. 首先，根据输入初始化一个 N×M 的迷宫，将障碍位置标记为不可通过。
2. 然后，从起点开始进行深度优先搜索。每次搜索时，都尝试向上下左右四个方向移动。
3. 如果移动后的位置在迷宫内，且没有被访问过，且不是障碍，则继续从这个位置进行深度优先搜索。
4. 如果移动后的位置就是终点，那么就找到了一条从起点到终点的路径，方案数加一。
5. 搜索完一个位置后，要将其标记为未访问，以便其他路径可以经过这个位置。
6. 因为这道题数据范围较小，答案与路径有关，所以我们选用DFS

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void dfs(int x, int y); // 深度优先搜索函数
int N, M, SX, SY, FX, FY, ans; // 定义全局变量
int maze[10][10]; // 定义迷宫和访问标记数组
int visited[10][10];
int dx[4] = {-1,  0, 1, 0}; // 定义四个方向的移动，上右下左
int dy[4] = {0, 1, 0, -1}; // 上右下左

int main(int argc, char *argv[])
{
	int T, i, x, y;
	scanf("%d %d %d", &N, &M, &T);
	scanf("%d %d %d %d", &SX, &SY, &FX, &FY);
	ans = 0;
	memset (maze, 0, sizeof(maze)); // 初始化迷宫和访问标记数组
	memset (visited, 0, sizeof (visited));
	
	for (i = 1; i <= T; i++) // 标记障碍位置
	{
		scanf("%d %d", &x, &y);
		maze[x][y] = 1;
	}
	visited[SX][SY] = 1; // 从起点开始深度优先搜素
	dfs(SX, SY);
	printf("%d\n", ans); // 输出方案总数
	return 0;
}

void dfs(int x, int y) // 深度优先搜索函数
{
	int i, nx, ny;
	if (x == FX && y == FY) // 如果到达终点
	{
		ans++; // 找到一条路径，方案数加一
		return; // 一旦找到目标，停止搜索，回溯到上一步，然后尝试其他可能的路径
	}
	for (i = 0; i < 4; i++) // 尝试四个方向的移动
	{
		nx = x + dx[i];
		ny = y + dy[i];
		// 判断新位置是非在迷宫内，且没有被访问过，且不是障碍
		if (nx >= 1 && nx <= N && ny >= 1 && ny <= N && visited[nx][ny] == 0 && maze[nx][ny] == 0)
		{
			visited[nx][ny] = 1; // 标记为已访问
			dfs(nx, ny); // 从新位置继续深度搜索
			visited[nx][ny] = 0; // 搜索完后，标记为未访问
		}
	}
}

广度优先搜索（BFS）

例题

马的遍历

题目描述

有一个 $n\times m$ 的棋盘，在某个点 $(x,y)$ 上有一个马，要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

输入只有一行四个整数，分别为 $n,m,x,y$。

输出格式

一个 $n\times m$ 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 $?1$）。

样例 #1

样例输入 #1

3 3 1 1

样例输出 #1

0    3    2    
3    -1   1    
2    1    4

提示

数据规模与约定

对于全部的测试点，保证 $1\le x\le n\le 400$，$1\le y\le m\le 400$。

题解

1. 初始化一个 n×m 的矩阵，所有的值都设为 ?1，表示马还没有访问过这个位置。
2. 将马的初始位置设为 0，表示马已经在这个位置上。
3. 创建一个队列，并将马的初始位置加入队列。
4. 当队列不为空时，取出队列的第一个元素，然后遍历马可以移动的所有位置（一共有8个方向）。对于每一个可以移动的位置，如果马还没有访问过，并且没有超出棋盘的边界，那么就将这个位置加入队列，并更新这个位置的步数（当前步数+1）。
5. 重复步骤4，直到队列为空。

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void bfs(int n, int m, int x, int y);
#define MAX 500
int dx[8] = {-2, -1, 1, 2, 2, 1, -1, -2}; // 马可以移动的8个方向
int dy[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int queue[MAX * MAX][2]; // 定义队列，用于存储待访问的位置
int board[MAX][MAX]; // 定义棋盘，用于存储每个位置的步数

int main(int argc, char *argv[])
{
	int n, m, x, y, i, j;
	scanf("%d %d %d %d", &n, &m, &x, &y);
	bfs(n, m, x - 1, y - 1); // 调用bfs函数，计算每个位置的步数
	for (i = 0; i < n; i++) // 输出结果
	{
		for (j = 0; j < m; j++)
		{
			printf("%d ", board[i][j]);
		}
		printf("\n");
	}
	return 0;
}

void bfs(int n, int m, int x, int y)
{
	int i, j;
	for (i = 0; i < n; i++) // 初始化棋盘，所有位置的步数都设为-1
	{
		for (j = 0; j < m; j++)
		{
			board[i][j] = -1;
		}
	}
	board[x][y] = 0; // 马的初始位置的步数设为0
	int front = 0, rear = 0; // // 创建队列，并将马的初始化位置加入队列
	queue[rear][0] = x; // 新元素总是被添加到到尾部
	queue[rear++][1] = y; // 是储存到同一个位置，并且rear++（后置递增操作）使得尾部位置向后移动一位，为下一个元素的添加做好准备
	
	while (front != rear) // 当队列不为空时（头部位置不等于尾部位置），进入循环
	{
		x = queue[front][0]; // 取出队列的第一个元素 
		y = queue[front++][1]; // 并将头部位置向后移动一位，为下一个元素的处理做好准备
		for (i = 0; i < 8; i++) // 遍历马可以移动的所有位置
		{
			int nx = x + dx[i], ny = y + dy[i];
			// 检查新位置是否在棋盘内，并且是否已经被访问过
			if (nx >= 0 && nx < n && ny >= 0 && ny < m && board[nx][ny] == -1)
			{
				queue[rear][0] = nx; // 将新位置加入队列，并更新步数
				queue[rear++][1] = ny;
				board[nx][ny] = board[x][y] + 1;
			}
		}
	}
}

填涂颜色

题目描述

由数字 $0$ 组成的方阵中，有一任意形状的由数字 $1$ 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 $2$。例如：$6\times 6$ 的方阵（$n=6$），涂色前和涂色后的方阵如下：

如果从某个 $0$ 出发，只向上下左右 $4$ 个方向移动且仅经过其他 $0$ 的情况下，无法到达方阵的边界，就认为这个 $0$ 在闭合圈内。闭合圈不一定是环形的，可以是任意形状，但保证闭合圈内的 $0$ 是连通的（两两之间可以相互到达）。

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 1 0 1
1 1 1 1 1 1

0 0 0 0 0 0
0 0 0 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 1 2 1
1 1 1 1 1 1

输入格式

每组测试数据第一行一个整数 $n(1\le n\le 30)$。

接下来 $n$ 行，由 $0$ 和 $1$ 组成的 $n\times n$ 的方阵。

方阵内只有一个闭合圈，圈内至少有一个 $0$。

输出格式

已经填好数字 $2$ 的完整方阵。

样例 #1

样例输入 #1

6
0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 0 0 1
1 1 0 0 0 1
1 0 0 0 0 1
1 1 1 1 1 1

样例输出 #1

0 0 0 0 0 0
0 0 1 1 1 1
0 1 1 2 2 1
1 1 2 2 2 1
1 2 2 2 2 1
1 1 1 1 1 1

提示

对于 $100\%$ 的数据，$1\le n\le 30$。

题解

当然可以，以下是这个问题的解题过程：

1. 确定解题方法：这是一个图论问题，可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来解决。我们选择使用BFS方法。

2. 编写代码：我们首先定义了四个方向的移动，然后定义了一个广度优先搜索的函数。这个函数会对所有的0进行搜索，如果一个0可以通过上下左右四个方向的移动到达边界，那么这个0就不在闭合圈内，我们将其标记为-1。然后，我们遍历整个方阵，将所有未被访问过的0（即在闭合圈内的0）填充为2，最后输出填充后的方阵。

代码

#include <stdio.h>
#include <stdlib.h>
void bfs(int x, int y);
#define MAXN 1000
int dx[4] = {0, 1, 0, -1}; // 定义四个方向的移动，右下左上
int dy[4] = {1, 0, -1, 0};
int queue[MAXN * MAXN][2]; // 定义队列，用于广度优先搜索
int g[MAXN][MAXN]; // 定义方阵
int n; // 方阵的大小

int main(int argc, char *argv[])
{
	int i, j;
	scanf("%d", &n);// 输入方阵的大小
	for (i = 0; i < n; i++) // 输入方阵
	{
		for (j = 0; j < n; j++)
		{
			scanf("%d", &g[i][j]);
		}
	}
	for (i = 0; i < n; i++) // 对方阵的边界进行搜索
	{
		if (g[i][0] == 0)
		{
			bfs(i, 0);
		}
		if (g[i][n - 1] == 0)
		{
			bfs(i, n - 1);
		}
	}
	for (i = 0; i < n; i++)
	{
		if (g[0][i] == 0)
		{
			bfs(0, i);
		}
		if (g[n - 1][i] == 0)
		{
			bfs(n - 1, i);
		}
	}
	for (i = 0; i < n; i++) // 输出填充后的方阵
	{
		for (j = 0; j < n; j++)
		{
			if (g[i][j] == -1)
			{
				g[i][j] = 0;
			}
			else if (g[i][j] == 0)
			{
				g[i][j] = 2;
			}
			printf("%d ", g[i][j]);
		}
		printf("\n");
	}
	return 0;
}

void bfs(int x, int y)
{
	int i, j, nx, ny;
	int front = 0, rear = 0; // 初始化队列头和尾
    g[x][y] = -1; // 将当前位置标记为-1，并加入队列
	queue[rear][0] = x;
	queue[rear++][1] = y;
	
	while (front != rear) // 当队列不为空时，继续搜索
	{
		x = queue[front][0]; // 取出循环的第一个元素
		y = queue[front++][1];
		for (i = 0; i < 4; i++) // 对当前的四个方向进行搜索
		{
			nx = x + dx[i];
			ny = y + dy[i];
			// 如果新的位置在方阵内，并且是0，则将其标记为-1，并加入队列
			if (nx >= 0 && nx < n && ny >= 0 && ny < n && g[nx][ny] == 0)
			{
				g[nx][ny] = -1;
				queue[rear][0] = nx;
				queue[rear++][1] = ny;
			}
		}
	}
}