C语言-算法-搜索

发布时间:2024年01月23日

深度优先搜索(DFS)

例题

迷宫

题目描述

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

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

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

输入格式

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

第二行为四个正整数 S X , S Y , F X , F Y SX,SY,FX,FY SX,SY,FX,FY S X , S Y SX,SY SX,SY 代表起点坐标, F X , F Y FX,FY FX,FY 代表终点坐标。

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

输出格式

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

样例 #1
样例输入 #1
2 2 1
1 1 2 2
1 2
样例输出 #1
1
提示

对于 100 % 100\% 100% 的数据, 1 ≤ N , M ≤ 5 1 \le N,M \le 5 1N,M5 1 ≤ T ≤ 10 1 \le T \le 10 1T10 1 ≤ S X , F X ≤ n 1 \le SX,FX \le n 1SX,FXn 1 ≤ S Y , F Y ≤ m 1 \le SY,FY \le m 1SY,FYm

题解
  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 × m n \times m n×m 的棋盘,在某个点 ( x , y ) (x, y) (x,y) 上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。

输入格式

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

输出格式

一个 n × m n \times m n×m 的矩阵,代表马到达某个点最少要走几步(不能到达则输出 ? 1 -1 ?1)。

样例 #1
样例输入 #1
3 3 1 1
样例输出 #1
0    3    2    
3    -1   1    
2    1    4
提示
数据规模与约定

对于全部的测试点,保证 1 ≤ x ≤ n ≤ 400 1 \leq x \leq n \leq 400 1xn400 1 ≤ y ≤ m ≤ 400 1 \leq y \leq m \leq 400 1ym400

题解
  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 0 0 组成的方阵中,有一任意形状的由数字 1 1 1 构成的闭合圈。现要求把闭合圈内的所有空间都填写成 2 2 2。例如: 6 × 6 6\times 6 6×6 的方阵( n = 6 n=6 n=6),涂色前和涂色后的方阵如下:

如果从某个 0 0 0 出发,只向上下左右 4 4 4 个方向移动且仅经过其他 0 0 0 的情况下,无法到达方阵的边界,就认为这个 0 0 0 在闭合圈内。闭合圈不一定是环形的,可以是任意形状,但保证闭合圈内 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 ≤ n ≤ 30 ) n(1 \le n \le 30) n(1n30)

接下来 n n n 行,由 0 0 0 1 1 1 组成的 n × n n \times n n×n 的方阵。

方阵内只有一个闭合圈,圈内至少有一个 0 0 0

输出格式

已经填好数字 2 2 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 % 100\% 100% 的数据, 1 ≤ n ≤ 30 1 \le n \le 30 1n30

题解

当然可以,以下是这个问题的解题过程:

  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;
			}
		}
	}
}
文章来源:https://blog.csdn.net/2301_79837864/article/details/135742892
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。