蛮力算法之深度优先遍历和广度优先遍历——图的深度优先遍历和广度优先遍历，附带案例：迷宫问题及矩阵中传染性传播问题

算法：图的深度优先搜索和广度优先搜索

这两种搜索方法本质上都是基于蛮力法思路

这两种搜索方法对有向图和无向图都适用

文章目录

  • 算法：图的深度优先搜索和广度优先搜索
    • 1 图的两种定义方式
      • 1.1 邻接矩阵
      • 1.2 邻接表
    • 2 图的深度优先遍历
    • 3 图的广度优先遍历
    • 案例
      • 案例1：迷宫
      • 案例2：传染
      • 案例3：跳动方格

1 图的两种定义方式

1.1 邻接矩阵

constexpr auto MAXV = 1000; //定义最大顶点个数

//顶点信息
typedef struct
{
	int no;
	char data[MAXV];
}VertexType;

//矩阵信息
typedef struct
{
	int edges[MAXV][MAXV];
	int n, e;
	VertexType vexs[MAXV];
}MGraph;

邻接矩阵示意图：

juz

1.2 邻接表

注意：边结点代表的是图中的边，而并非图中的结点；头结点才表示图中的结点；头结点身后所连接的为边结点

//边结点 
typedef struct ANode
{
	int adjvex;			//这条边的终点
	int weight;			//这条边的权重
	struct ANode* nextarc;  //指向下一条与该结点相邻的边
} ArcNode;


//头结点
typedef struct VNode
{
	string date;		//顶点的其他信息
	ArcNode* firstarc;	//指向第一条边
};


//邻接表
typedef struct
{
	VNode adjList[MAXV];  //头结点组成的数组
	int n, e;            //图中的顶点数n和边数e
}ALGraph;

邻接表示意图：（一般默认为出边表）

biao

2 图的深度优先遍历

关键：

  1. 用**visited[]**数组记录是否已访问
  2. 这是一个递归的过程

邻接矩阵的：

void DFS(MGraph g,int v)
{	int w;
	cout<<v<<" ";						//输出被访问顶点的编号
	visited[v]=1;						//置已访问标记
	for (w=0;w<g.n;w++)					//找顶点v的所有相邻点
		if (g.edges[v][w]!=0 && g.edges[v][w]!=INF && visited[w]==0)
			DFS(g,w);					//找顶点v的未访问过的相邻点w
}

邻接表的：

void DFS(ALGraph *G,int v)
{	ArcNode *p;
	cout<<v<<" ";					//输出被访问顶点的编号
	visited[v]=1;						//置已访问标记
	p=G->adjlist[v].firstarc;			//p指向顶点v的第一个邻接点
	while (p!=NULL)
	{	if (visited[p->adjvex]==0)		//若p->adjvex顶点未访问,递归访问它
			DFS(G,p->adjvex);
		p=p->nextarc;					//p指向顶点v的下一个邻接点
	}
}

3 图的广度优先遍历

关键：

  1. 使用数据结构 → 队列来记录未访问的邻接点
  2. 用**visited[]**数组记录哪些点已经访问了，哪些还没有
  3. 采用循环，循环终止条件为队列空了

邻接矩阵的：

void BFS(MGraph g,int v)					//邻接矩阵的DFS算法
{
	queue<int> qu;							//定义一个队列qu
	int visited[MAXV];						//定义存放结点的访问标志的数组
	int w,i;
	memset(visited,0,sizeof(visited));		//访问标志数组初始化

	cout<<v<<" ";						//输出被访问顶点的编号
	visited[v]=1;							//置已访问标记
	qu.push(v);								//v进队
	while (!qu.empty())						//队列不空时循环
	{
		w=qu.front(); qu.pop();				//出队顶点w
		for (i=0;i<g.n;i++)					//找与顶点w相邻的顶点
			if (g.edges[w][i]!=0 && g.edges[w][i]!=INF && visited[i]==0)
			{	//若当前邻接顶点i未被访问
				cout<<i<<" ";			//访问相邻顶点
				visited[i]=1;				//置该顶点已被访问的标志
				qu.push(i);					//该顶点进队
			}
	}
	printf("\n");
}

邻接表的：

void BFS(ALGraph *G,int v)					//邻接表的DFS算法
{
	ArcNode *p;
	queue<int> qu;							//定义一个队列qu
	int visited[MAXV];						//定义存放顶点的访问标志的数组
	int w;
	memset(visited,0,sizeof(visited));		//访问标志数组初始化
	cout<<v<<" ";						//输出被访问顶点的编号
	visited[v]=1; 							//置已访问标记
	qu.push(v);								//v进队
	while (!qu.empty())						//队列不空时循环
	{
		w=qu.front(); qu.pop();				//出队顶点w
		p=G->adjlist[w].firstarc;			//找顶点w的第一个邻接点
		while (p!=NULL) 
		{	if (visited[p->adjvex]==0)		//若当前邻接顶点未被访问
			{	cout<<i<<" ";	//访问相邻顶点
				visited[p->adjvex]=1;		//置该顶点已被访问的标志
				qu.push(p->adjvex);			//该顶点进队
			}
			p=p->nextarc;					//找顶点w的下一个邻接点
		}
	}
	printf("\n");
}

两种遍历方式都重点掌握邻接表的。

案例

案例1：迷宫

【问题描述】有如下8*8的迷宫图：

OXXXXXXX
OOOOOXXX
XOXXOOOX
XOXXOXXO
XOXXXXXX
XOXXOOOX
XOOOOXOO
XXXXXXXO

其中，O表示通路方块，X表示障碍方块。假设入口是位置（0，0），出口为右下角方块位置（7，7）。设计一个程序采用递归方法求指定入口到出口的一条迷宫路径。

深度优先的解法：

关键：

  1. 用数组记录垂直与水平偏移量，才能运用for循环遍历来尝试各种可能
  2. 采用递归，递归的终止条件为达到了终点
  3. 如何记录过程（路径）？在深度遍历的过程中，将可行的点作上了记号，不可行的点保留了原貌；最后输出矩阵即可
#include <stdio.h>
#define MAxN 10						//最大迷宫大小
//问题表示
int n=8;							//迷宫大小
char Maze[MAxN][MAxN]=
{	{'O','X','X','X','X','X','X','X'},
	{'O','O','O','O','O','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','X','X','O','X','X','O'},
	{'X','O','X','X','X','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','O','O','O','X','O','O'},
	{'X','X','X','X','X','X','X','O'}
};
int H[4] = {0, 1, 0, -1};			//水平偏移量,下标对应方位号0～3
int V[4] = {-1, 0, 1, 0};			//垂直偏移量

void disppath()						//输出一条迷宫路径
{
	for (int i=0; i<n;i++)
	{
		printf("    ");
		for(int j=0; j<n;j++)
			printf("%c",Maze[i][j]);
		printf("\n");
	}
}
void DFS(int x,int y)			 //求从(x,y)出发的一条迷宫路径
{
	if (x==n-1 && y==n-1) //找到一条路径,输出
	{
		Maze[n-1][n-1]=' ';
		disppath();
		return;
	}
	else
	{	for (int k=0;k<4;k++)				 //试探每一个方位
			if(x>=0 && y>=0 && x<n && y<n && Maze[x][y]=='O')
			{								//若(x,y)方块的可走的
				Maze[x][y]=' ';				//将该方块设置为空字符
				DFS(x+V[k],y+H[k]);			//查找(x,y)周围的每一个相邻方块
				Maze[x][y]='O';				//若从该相邻方块出发没有找到路径,恢复(x,y)
			}
	}
}
void main()
{
	int x=0,y=0;		//指定入口,出口默认为(n-1,n-1)
	printf("一条迷宫路径:\n");
	DFS(x,y);			//求(0,0)->(7,7)的一条迷宫路径
}

广度优先的解法：

关键：

  1. 用数组记录垂直与水平偏移量，才能运用for循环遍历来尝试各种可能
  2. 如何记录路径：采用队列，对于可行的方块，我们将其放入队列尾部（方块是用结构体定义的）
  3. 不会记录到多条路径吗？是的，队列中除了结果路径的点之外，还有广度遍历过程中其他路径上的点，所以，我们要用结构体来定义点，并赋予一个属性pre，用来记录这个点的前驱在队列中的下标（用数组加上队头队尾组成的队列支持随机访问）
  4. 在将方块添加到队列之前，要将其修改为某个特定的值防止其被再次访问到。例如A之后的B可行，接下来我们要以B为对象，判断它周围的方块是否可行，A也是其周围方块之一，但是不用再访问A了，因为之前已经访问过了
#include <stdio.h>
#define MAXQ 100					//队列大小
#define MAxN 10						//最大迷宫大小
//问题表示
int n=8;							//迷宫大小
char Maze[MAxN][MAxN]=
{	{'O','X','X','X','X','X','X','X'},
	{'O','O','O','O','O','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','X','X','O','X','X','O'},
	{'X','O','X','X','X','X','X','X'},
	{'X','O','X','X','O','O','O','X'},
	{'X','O','O','O','O','X','O','O'},
	{'X','X','X','X','X','X','X','O'}
};
int H[4] = {0, 1, 0, -1};			//水平偏移量,下标对应方位号0～3
int V[4] = {-1, 0, 1, 0};			//垂直偏移量
struct Position						//队列元素类型
{
	int x,y;						//当前方块位置
	int pre;						//前驱方块的下标
};
Position qu[MAXQ];					//定义一个队列qu
int front=-1,rear=-1;				//定义队头和队尾

void disppath(int front)			//输出一条迷宫路径
{
	int i,j;
	for (i=0; i<n;i++)				//将所有'*'改为'O'
		for (j=0;j<n;j++)
			if (Maze[i][j]=='*')
				Maze[i][j]='O';
	int k=front;
	while (k!=-1)					//即路径上的方块改为' '
	{
		Maze[qu[k].x][qu[k].y]=' ';
		k=qu[k].pre;
	}
	for (i=0; i<n;i++)				//输出迷宫路径
	{	printf("    ");
		for(int j=0; j<n;j++)
			printf("%c",Maze[i][j]);
		printf("\n");
	}
}

void BFS(int x,int y)			 //求从(x,y)出发的一条迷宫路径
{
	Position p,p1,p2;
	p.x=x; p.y=y; p.pre=-1;			//建立入口结点
	Maze[p.x][p.y]='*';				//改为'*'避免重复查找
	rear++; qu[rear]=p;				//入口方块进队
	while (front!=rear)				//队不空循环
	{
		front++; p1=qu[front];		//出队方块p1;
		if (p1.x==n-1 && p1.y==n-1)	//找到出口
		{
			disppath(front);		//输出路径
			return;
		}
		for (int k=0;k<4;k++)		//试探p1的每个相邻方位
		{
			p2.x=p1.x+V[k];			//找到p1的相邻方块p2
			p2.y=p1.y+H[k];
			if (p2.x>=0 && p2.y>=0 && p2.x<n && p2.y<n && Maze[p2.x][p2.y]=='O')
			{	//方块p2有效并且可走
				Maze[p2.x][p2.y]='*';	//改为'*'避免重复查找
				p2.pre=front;
				rear++;	qu[rear]=p2;	//方块p2进队
			}
		}
	}
}
void main()
{
	int x=0,y=0;		//指定入口,出口默认为(n-1,n-1)
	printf("一条迷宫路径:\n");
	BFS(x,y);			//求(0,0)->(7,7)的一条迷宫路径
}

案例2：传染

这个案例可以更好的理解广度优先遍历

小蓝有一个01矩阵。他打算将第一行第一列的 0 变为 2 。变化过程有传染性，每次 2 的上下左右四个相邻的位置中的 0 都会变成 2 。直到最后每个 2 的周围都是 1 或 2 结束。
请问，最终矩阵中有多少个 2 ？
以下是小蓝的矩阵，共 30 行 40 列。

0000100010000001101010101001001100000011
0101111001111101110111100000101010011111
1000010000011101010110000000001011010100
0110101010110000000101100100000101001001
0000011010100000111111001101100010101001
0110000110000000110100000000010010100011
0100110010000110000000100010000101110000
0010011010100110001111001101100110100010
1111000111101000001110010001001011101101
0011110100011000000001101001101110100001
0000000101011000010011111001010011011100
0000100000011001000100101000111011101100
0010110000001000001010100011000010100011
0110110000100011011010011010001101011011
0000100100000001010000101100000000000010
0011001000001000000010011001100101000110
1110101000011000000100011001001100111010
0000100100111000001101001000001010010001
0100010010000110100001100000110111110101
1000001001100010011001111101011001110001
0000000010100101000000111100110010101101
0010110101001100000100000010000010110011
0000011101001001000111011000100111010100
0010001100100000011000101011000000010101
1001111010010110011010101110000000101110
0110011101000010100001000101001001100010
1101000000010010011001000100110010000101
1001100010100010000100000101111111111100
1001011010101100001000000011000110110000
0011000100011000010111101000101110110001

思路：广度优先遍历，当队列为空时为循环终止条件，计算矩阵中2的个数

#include<iostream>
#define MAXQ 100					
#define MAxN 100						
using namespace std;

int Maze[MAxN][MAxN] =
{ 
  {0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,0,1,0,1,0,1,0,0,1,0,0,1,1,0,0,0,0,0,0,1,1},
  {0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,1,1,1,1,1},
  {0,1,0,1,1,1,1,0,0,1,1,1,1,1,0,1,1,1,0,1,1,1,1,0,0,0,0,0,1,0,1,0,1,0,0,1,1,1,1,1},
  {1,0,0,0,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,0,0,1,0,1,1,0,1,0,1,0,0},
  {0,1,1,0,1,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,1,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,1},
  {0,0,0,0,0,1,1,0,1,0,1,0,0,0,0,0,1,1,1,1,1,1,0,0,1,1,0,1,1,0,0,0,1,0,1,0,1,0,0,1},
  {0,1,1,0,0,0,0,1,1,0,0,0,0,0,0,0,1,1,0,1,0,0,0,0,0,0,0,0,0,1,0,0,1,0,1,0,0,0,1,1},
  {0,1,0,0,1,1,0,0,1,0,0,0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,0,1,0,1,1,1,0,0,0,0},
  {0,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,0,1,1,1,1,0,0,1,1,0,1,1,0,0,1,1,0,1,0,0,0,1,0},
  {1,1,1,1,0,0,0,1,1,1,1,0,1,0,0,0,0,0,1,1,1,0,0,1,0,0,0,1,0,0,1,0,1,1,1,0,1,1,0,1},
  {0,0,1,1,1,1,0,1,0,0,0,1,1,0,0,0,0,0,0,0,0,1,1,0,1,0,0,1,1,0,1,1,1,0,1,0,0,0,0,1},
  {0,0,0,0,0,0,0,1,0,1,0,1,1,0,0,0,0,1,0,0,1,1,1,1,1,0,0,1,0,1,0,0,1,1,0,1,1,1,0,0},
  {0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,0,0,1,0,0,1,0,1,0,0,0,1,1,1,0,1,1,1,0,1,1,0,0},
  {0,0,1,0,1,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,0,1,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,1},
  {0,1,1,0,1,1,0,0,0,0,1,0,0,0,1,1,0,1,1,0,1,0,0,1,1,0,1,0,0,0,1,1,0,1,0,1,1,0,1,1},
  {0,0,0,0,1,0,0,1,0,0,0,0,0,0,0,1,0,1,0,0,0,0,1,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0},
  {0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,1,1,0,0,1,1,0,0,1,0,1,0,0,0,1,1,0},
  {1,1,1,0,1,0,1,0,0,0,0,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,0,0,1,1,0,0,1,1,1,0,1,0},
  {0,0,0,0,1,0,0,1,0,0,1,1,1,0,0,0,0,0,1,1,0,1,0,0,1,0,0,0,0,0,1,0,1,0,0,1,0,0,0,1},
  {0,1,0,0,0,1,0,0,1,0,0,0,0,1,1,0,1,0,0,0,0,1,1,0,0,0,0,0,1,1,0,1,1,1,1,1,0,1,0,1},
  {1,0,0,0,0,0,1,0,0,1,1,0,0,0,1,0,0,1,1,0,0,1,1,1,1,1,0,1,0,1,1,0,0,1,1,1,0,0,0,1},
  {0,0,0,0,0,0,0,0,1,0,1,0,0,1,0,1,0,0,0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,1},
  {0,0,1,0,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,1,0,0,0,0,0,0,1,0,0,0,0,0,1,0,1,1,0,0,1,1},
  {0,0,0,0,0,1,1,1,0,1,0,0,1,0,0,1,0,0,0,1,1,1,0,1,1,0,0,0,1,0,0,1,1,1,0,1,0,1,0,0},
  {0,0,1,0,0,0,1,1,0,0,1,0,0,0,0,0,0,1,1,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,0,1,0,1,0,1},
  {1,0,0,1,1,1,1,0,1,0,0,1,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,0,0,0,0,0,0,0,1,0,1,1,1,0},
  {0,1,1,0,0,1,1,1,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,0,0,1,0,1,0,0,1,0,0,1,1,0,0,0,1,0},
  {1,1,0,1,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,0,0,1,0,0,0,1,0,0,1,1,0,0,1,0,0,0,0,1,0,1},
  {1,0,0,1,1,0,0,0,1,0,1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,1,0,1,1,1,1,1,1,1,1,1,1,1,0,0},
  {1,0,0,1,0,1,1,0,1,0,1,0,1,1,0,0,0,0,1,0,0,0,0,0,0,0,1,1,0,0,0,1,1,0,1,1,0,0,0,0},
  {0,0,1,1,0,0,0,1,0,0,0,1,1,0,0,0,0,1,0,1,1,1,1,0,1,0,0,0,1,0,1,1,1,0,1,1,0,0,0,1}
};


int H[4] = { 0, 1, 0, -1 };			//水平偏移量,下标对应方位号0～3
int V[4] = { -1, 0, 1, 0 };			//垂直偏移量

struct Position						//队列元素类型
{
	int x, y;						//当前方块位置
};

Position qu[MAXQ];					//定义一个队列qu
int front = -1, rear = -1;			//定义队头和队尾


//输出迷宫并输出迷宫中的2的个数
void print_2()
{
	int count = 0;
	for (int i = 0; i < 30; i++)
	{
		for (int j = 0; j < 40; j++)
		{
			cout << Maze[i][j];
			if (Maze[i][j] == 2)
			{
				count++;
			}
		}
		cout << endl;
	}
	cout << "迷宫中2的个数为：" << count << endl;
}


void BFS(int x, int y)			 //求从(x,y)出发的一条迷宫路径
{
	Position p, p1, p2;
	p.x = x; p.y = y; 		//建立入口结点
	Maze[p.x][p.y] = 2;				//改为2避免重复查找
	rear++; qu[rear] = p;				//入口方块进队
	while (front != rear)				//队不空循环
	{
		front++; p1 = qu[front];		//出队方块p1;
		for (int k = 0; k < 4; k++)		//试探p1的每个相邻方位
		{
			p2.x = p1.x + V[k];			//找到p1的相邻方块p2
			p2.y = p1.y + H[k];
			if (p2.x >= 0 && p2.y >= 0 && p2.x < 30 && p2.y < 40 && Maze[p2.x][p2.y] == 0)
			{	//方块p2有效并且可走
				Maze[p2.x][p2.y] = 2;	//改为2避免重复查找
				rear++;	qu[rear] = p2;	//方块p2进队
			}
		}
	}
	print_2();
}

int main()
{
	int x = 0, y = 0;		
	BFS(x, y);
	return 0;
}

输出结果：

image-20231206204319567

案例3：跳动方格

如果两个相邻方格（上下左右四个方向相邻）内的数的最大公约数大于 1 ，则可以从其中一个方格移动到另一个方格，当然也可以从另一个方格移回第一个方格。
假设开始时站在第 r 行第 c 列，请问可以移动到方格图内的多少个方格？

样例输入

3 4
3 6 5 5
2 4 3 5
7 8 3 8
3 2

样例输出

5

思路：采用广度优先遍历，在将可行的方格放入到队列之前，计数+1

易错点+技巧点：

二维数组的初始化；

用同样尺寸的数组记录某个位置是否已经被访问过了；

没有记录路线的要求就可以不使用pre属性

二维数组的动态初始化：

//动态定义一个二维数组，并将其全部值初始化为0
	int** map;
	map = new int* [m];
	
	for (int i = 0; i < m; i++)
	{
        int* row = new int[n];
		for (int j = 0; j < n; j++)
		{
			row[j] = 1;
		}
		map[i] = row;
	}

或者

//动态定义一个二维数组，并将其全部值初始化为0
	int** map;
	map = new int* [m];

	for (int i = 0; i < m; i++)
	{
		map[i] = new int[n];
		for (int j = 0; j < n; j++)
		{
			map[i][j] = 1;
		}
	}

使用memset

int** map = new int* [m];
for (int i = 0; i < m; ++i) {
	map[i] = new int[n];
	memset(map[i], 3, n * sizeof(int));
}

#include<iostream>
#define MAXQ 100					//队列大小
#define MAxN 100						//最大迷宫大小
using namespace std;

int** map;
int** flag;	//记录是否已经被访问了
int m;
int n;

int H[4] = { 0, 1, 0, -1 };			//水平偏移量,下标对应方位号0～3
int V[4] = { -1, 0, 1, 0 };			//垂直偏移量

struct Position						//队列元素类型
{
	int x, y;//当前方块位置
};

Position qu[MAXQ];					//定义一个队列qu
int front = -1, rear = -1;			//定义队头和队尾

bool moreThanOne(int x, int y)
{
	//两个数的最大公约数大于1，返回true
	int theSmallOne = x < y ? x : y;
	for (int i = 2; i <= theSmallOne; i++)
	{
		if (x % i == 0 && y % i == 0) return true;
	}
	return false;
}

void printMap()
{
	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			cout << map[i][j]<<"  ";
		}
		cout << endl;
	}
}

void BFS(int x, int y)			 
{
	int count = 0;          //记录可以跳跃的个数
	Position p, p1, p2;
	p.x = x; p.y = y; 		//建立入口结点			
	rear++; qu[rear] = p;		
	count++;

	while (front != rear)				//队不空循环
	{
		front++; p1 = qu[front];		//出队方块p1;
		for (int k = 0; k < 4; k++)		//试探p1的每个相邻方位
		{
			p2.x = p1.x + V[k];			//找到p1的相邻方块p2
			p2.y = p1.y + H[k];

			if (p2.x >= 0 && p2.y >= 0 && p2.x < m && p2.y < n && moreThanOne(map[p2.x][p2.y], map[p1.x][p1.y]) && flag[p2.x][p2.y] != -1)
			{
				//方块p2有效并且可走
				flag[p1.x][p1.y] = -1;	//改为-1避免重复查找
				rear++;	qu[rear] = p2;	//方块p2进队
				count++;
			}
		}
	}

	printMap();
	cout << count << endl;
}

int main()
{
	//初始化矩阵
	cin >> m >> n;
	map = new int* [m];       //动态初始化二维数组这一步很重要，但是这一步最容易忘
	flag = new int* [m];
	for (int i = 0; i < m; i++)
	{
		int* row = new int[n];
		int* flag_row = new int[n];
		for (int j = 0; j < n; j++)
		{
			cin >> row[j];
			flag_row[j] = 0;
		}
		map[i] = row;
		flag[i] = flag_row;
	}

	//输入初始化的位置
	int x, y;
	cin >> x >> y;
	BFS(x - 1, y - 1);

	return 0;
}

运行结果：

image-20231207151238260

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/238047.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ArkUI List组件

ArkUI List组件

我们在column中使用foreach循环渲染数据的时候&#xff0c;如果数据过多&#xff0c;超出屏幕高度&#xff0c;会出现隐藏的情况。 class Item {name: stringimage: ResourceStrprice: numberdiscount: numberconstructor(name: string, image: ResourceStr, price: number,dis…
阅读更多...
【项目小结】优点分析

【项目小结】优点分析

一、 个人博客系统 一&#xff09;限制强制登录 问题&#xff1a;限制用户登录后才能进行相关操作解决&#xff1a; 1&#xff09;前端&#xff1a; ① 写一个函数用于判断登录状态&#xff0c;如果返回的状态码是200就不进行任何操作&#xff0c;否则Ajax实现页面的跳转操作…
阅读更多...
Python房价分析（二）随机森林分类模型

Python房价分析（二）随机森林分类模型

目录 1 数据预处理 1.1 房价数据介绍 1.2 数据预处理 1.2.1 缺失值处理 1.2.2异常值处理 1.2.3 数据归一化 1.2.4 分类特征编码 2 随机森林模型 2.1 模型概述 2.2 建模步骤 2.3 参数搜索过程 3模型评估 3.1 模型评估结果 3.2 混淆矩阵 3.3 绘制房价类别三分类的…
阅读更多...
推荐系统，“广告Match底层技术”中的名词（TDM、HNSW、PQ）

推荐系统，“广告Match底层技术”中的名词（TDM、HNSW、PQ）

召回&#xff1a;匹配 TDM&#xff1a;"树状深度模型"&#xff08;Tree-based Deep Model&#xff09;&#xff0c;是一种结合了树状结构和深度学习的模型&#xff0c;主要用于解决大规模推荐系统中的候选项生成&#xff08;candidate generation&#xff09;问题。在…
阅读更多...
多种DC电源模块的比较和评价

多种DC电源模块的比较和评价

多种DC电源模块的比较和评价 BOSHIDA DC电源模块是一种重要的电子零件&#xff0c;可以将交流电转换为直流电&#xff0c;并为相应的电路提供所需的电能。随着技术的进步&#xff0c;市场上的DC电源模块种类越来越多&#xff0c;不同类型的DC电源模块有着不同的特点和优缺点。 …
阅读更多...
数据结构-05-跳表SkipList

数据结构-05-跳表SkipList

1-什么是跳表 跳表SkipList是一种随机化的数据结构&#xff0c;基于并联的链表&#xff0c;实现简单&#xff0c;插入、删除、查找的复杂度均为 O(logN)&#xff08;大多数情况下&#xff0c;因为是实现上是概率问题&#xff09;&#xff0c;因为其性能匹敌红黑树且实现较为简单…
阅读更多...
jetpack compose 学习(-)

jetpack compose 学习(-)

年底了,无聊的时间总是缓慢的,找个事情做一做,打发打发时间,刚好看到jetpack compose 学习学习,毕竟androidStudio 默认创建的项目都带上了这个,学习网站:https://developer.android.com/jetpack/compose/modifiers?hlzh-cn 1. 首先androidStudio创建一个新项目 喜欢kotlin的,…
阅读更多...
面向工业物联网的5G机器学习研究综述

面向工业物联网的5G机器学习研究综述

源自&#xff1a;信息与控制 作者&#xff1a;柴浩轩 金曦 许驰 夏长清 摘 要 随着计算机技术不断应用于工业物联网&#xff0c;工业系统中的数据传输愈加需要支持高实时、高可靠、高带宽以及海量连接的特性。传统的网络已经无法满足这些需求&#xff0c;5G网络因其高速率…
阅读更多...
ASO优化之如何在应用商城突围

ASO优化之如何在应用商城突围

再好的内容没有营销也很难成功。评判一个APP是否在应用市场获得关注的一个重要标准就是下载量。但是&#xff0c;光被人发现你的APP应用是没有用的&#xff0c;还要精确定位有需要的目标群体才能更好的推销出去。在制定合适的优化策略的&#xff0c;一定要对市场行情有一个比较…
阅读更多...
C# 图解教程 第5版 —— 第18章 泛型

C# 图解教程 第5版 —— 第18章 泛型

文章目录 18.1 什么是泛型18.2 C# 中的泛型18.3 泛型类18.3.1 声明泛型类18.3.2 创建构造类型18.3.3 创建变量和实例18.3.4 使用泛型的示例18.3.5 比较泛型和非泛型栈 18.4 类型参数的约束18.4.1 Where 子句18.4.2 约束类型和次序 18.5 泛型方法18.5.1 声明泛型方法18.5.2 调用…
阅读更多...
青少年CTF-Misc(持续更新中)

青少年CTF-Misc(持续更新中)

FLAG&#xff1a;当觉得自己很菜的时候&#xff0c;就静下心来学习 专研方向:Web安全&#xff0c;CTF 每日emo&#xff1a;听一千遍反方向的钟&#xff0c;我们能回到过去吗&#xff1f; 1.StegoTXT&#xff1a; 解压缩文件。发现字母中存在覆盖。使用0宽隐写在线解密得到flag…
阅读更多...
Slate基础使用说明

Slate基础使用说明

目录 Slate基础使用说明 1. 简单教程 2. 要点说明 2.1 TCommands以及TCommands基类 2.2 FUICommandInfo 2.3 FUICommandList 2.4 FUIAction 2.5 UICommand 3. 代码源码 4. 工具使用 4.1 Display Ul Extension Points 4. 参考文章 Slate基础使用说明 1.…
阅读更多...
设计模式02创建者模式

设计模式02创建者模式

创建者模式 参考网课:黑马程序员Java设计模式详解 博客笔记 创建型模式的主要关注点是“怎样创建对象&#xff1f;”&#xff0c;它的主要特点是“将对象的创建与使用分离”。 这样可以降低系统的耦合度&#xff0c;使用者不需要关注对象的创建细节。 创建型模式分为&#…
阅读更多...
下一代Wi-Fi技术：Wi-Fi 7(IEEE 802.11be EHT)

下一代Wi-Fi技术：Wi-Fi 7(IEEE 802.11be EHT)

文章目录 Wi-Fi 7名词解释Wi-Fi 7的产生背景Wi-Fi 7的发布时间Wi-Fi 7的技术优势Wi-Fi 7 vs Wi-Fi 6Wi-Fi 7支持的新特性支持最大320MHz带宽引入更高阶的4096-QAM调制技术MIMO 1616引入Multi-Link多链路机制Multi-RUPreamble Puncturing Wi-Fi 7的应用场景推荐阅读 Wi-Fi 7名词…
阅读更多...
DevEco Studio 生成HPK文件

DevEco Studio 生成HPK文件

DevEco Studio 生成HPK文件 一、安装环境 操作系统: Windows 10 专业版 IDE:DevEco Studio 3.1 SDK:HarmonyOS 3.1 二、生成HPK文件 生成的HPK文件存放在entry文件夹下。下图是未生成HPK的样式。 生成HPK&#xff1a;菜单Build->Build Hap(s)/APP(s)->Build Hap(s)…
阅读更多...
Python使用分段函数拟合数据

Python使用分段函数拟合数据

Python使用分段函数拟合数据 前言前提条件相关介绍实验环境使用分段函数拟合数据代码实现输出结果 前言 由于本人水平有限&#xff0c;难免出现错漏&#xff0c;敬请批评改正。更多精彩内容&#xff0c;可点击进入Python日常小操作专栏、OpenCV-Python小应用专栏、YOLO系列专栏…
阅读更多...
HCIA-H12-811题目解析（3）

HCIA-H12-811题目解析（3）

1、【单选题】 以下关于路由器的描述&#xff0c;说法错误的是&#xff1f; 2、【单选题】某网络工程师在输入命令行时提示如下信息&#xff1a;Error:Unrecognized command foun at position.对于该提示信息说法正确的是&#xff1f; 3、【单选题】如下图所示的网络&#xf…
阅读更多...
Vue3-03-reactive() 响应式基本使用

Vue3-03-reactive() 响应式基本使用

reactive() 的简介 reactive() 是vue3 中进行响应式状态声明的另一种方式&#xff1b; 但是&#xff0c;它只能声明 【对象类型】的响应式变量&#xff0c;【不支持声明基本数据类型】。reactive() 与 ref() 一样&#xff0c;都是深度响应式的&#xff0c;即对象嵌套属性发生了…
阅读更多...
数据科学工作的20个Pandas函数（备忘）

数据科学工作的20个Pandas函数（备忘）

Pandas 是数据科学社区中使用最广泛的库之一&#xff0c;它是一个强大的工具&#xff0c;可以进行数据操作、清理和分析。 本文将提供最常用的 Pandas 函数以及如何实际使用它们的样例。我们将涵盖从基本数据操作到高级数据分析技术的所有内容&#xff0c;到本文结束时&#xf…
阅读更多...
还在为论文焦虑？免费AI写作大师帮你三分钟搞定

还在为论文焦虑？免费AI写作大师帮你三分钟搞定

先来看1分钟的视频&#xff0c;对于要写论文的你来说&#xff0c;绝对有所值&#xff01; 还在为写论文焦虑&#xff1f;免费AI写作大师来帮你三步搞定 第一步&#xff1a;输入关键信息 第二步&#xff1a;生成大纲 稍等片刻后&#xff0c;专业大纲生成&#xff08;由于举例&am…
阅读更多...
最新文章

Copyright @ 2022~2023