友情链接交易网站源码,先备案先建网站,雄安投资建设集团有限公司网站,南宁网站建设哪家公司题目#xff1a;
1101. 献给阿尔吉侬的花束 - AcWing题库 输入样例#xff1a;
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.输出样例#xff1a;
5
1
oop!
思路#xff1a;bfs宽搜
用队列实现bfs。踢出队列头#xff0c;并在队列尾插入与对头相关的…题目
1101. 献给阿尔吉侬的花束 - AcWing题库 输入样例
3
3 4
.S..
###.
..E.
3 4
.S..
.E..
....
3 4
.S..
####
..E.输出样例
5
1
oop!
思路bfs宽搜
用队列实现bfs。踢出队列头并在队列尾插入与对头相关的xxx(往往是相邻点)。直至队列为空。这个过程相当于逐行遍历宽度优先搜索树。可以用于求最短路径。
拓展补充
BFSBreadth-First Search广度优先搜索是一种图算法用于遍历或搜索图中的节点。它从图的起始节点开始逐层地访问其相邻节点直到找到目标节点或遍历完整个图。
BFS通常使用队列来实现起始节点首先被放入队列中然后依次访问其相邻节点并将这些相邻节点加入队列。接着从队列中取出下一个节点重复上述过程直到队列为空为止。
BFS的特点是能够找到起始节点到目标节点的最短路径因为它先访问离起始节点最近的节点然后依次向外扩展。这使得BFS在寻找最短路径或最短距离的问题上非常有效。
BFS也可以用于检测图中的环路、连通性、拓扑排序等问题。它是一种简单而且常用的图算法被广泛应用于计算机科学领域的各种问题中。
代码
#includeiostream
#includecstdio
#includecstring//memset头文件
#includequeue
using namespace std;
typedef pairint, intPII;
#define x first
#define y second
PII Start, End;//表示起点和终点
const int N 210;
int m, n;//表示矩阵行列
int dist[N][N];//表示距离起点start的距离赋初值为-1,可以用于判重
char p[N][N];//表示矩阵某点坐标int bfs(PII Start, PII End)
{memset(dist, -1, sizeof dist);//设距离起点初始值为-1dist[Start.x][Start.y] 0;queuePIIq;//用队列实现宽搜bfsq.push(Start);while (q.size()) {PII t q.front();//取对列头q.pop();//将对头踢出队列int dx[4] { -1,1,0,0 }; int dy[4] { 0,0,-1,1 };for (int i 0; i 4; i) {int x t.x dx[i]; int y t.y dy[i];//不合规走法if (x 0 || x m || y 0 || y n)continue;//越界if (p[x][y] #)continue;//路障if (dist[x][y] ! -1)continue;//之前已经遍历过//合规走法dist[x][y] dist[t.x][t.y] 1;//在队列头t的基础上走出一步距离1q.push({ x,y });//将合规走法的坐标点加入队列尾部if (End make_pair(x, y))return dist[x][y];}}return -1;//表示走到不能走了都没有找到End即无法到达
}int main()
{int T;cin T;while (T--) {scanf(%d%d, m, n);for (int i 0; i m; i)scanf(%s, p[i]);//按行输入for(int i0;im;i)for (int j 0; j n; j) {if (p[i][j] S)Start { i,j };else if (p[i][j] E)End { i,j };}int distance bfs(Start, End);if (distance -1)cout oop! endl;else cout distanceendl;}}
