C++广度优先搜索一（练习题）-北京尧图网络

农夫与羊【描述】有有一个农夫有个nxm大小的农场农场的四周有墙把农场跟外面隔离开同时农场里也有一些隔离墙其余的是空地。农夫想养一些公羊但是公羊好斗而且公羊在农场里会“上下左右”四处走动(但不能穿过墙)两只公羊不能见面(见面就会顶角受伤)。为了不让公羊受伤农夫想知道他的农场最多能养几只公羊为了方便起见,农场的描述用0表示空地1表示墙。【输入格式】第一行输入n和m表示农场大小是nxm(1≤n,m≤1000)。接下来是一个nxm的矩阵,矩阵里每个值是0或者1。行内数之间用空格隔开。【输出格式】一行一个整数表示农夫能养的公羊数量。【输入样例】4 51 0 1 1 11 0 1 0 11 1 1 1 01 0 0 0 0【输出样例】3#includeiostream#includequeueusingnamespacestd;structnode{intx;//行inty;//列};queuenodeq;#defineMAXN1001// n,m的最大值1intn,m;intsx,sy;intmp[MAXN][MAXN];//地图0表示空地1表示墙boolvisited[MAXN][MAXN];intdir[4][2]{{0,1},{1,0},{0,-1},{-1,0}};//右下左上intcnt;//连通块数量voidbfs(){node s{sx,sy};visited[sx][sy]true;cnt;q.push(s);while(!q.empty()){node curq.front();q.pop();for(inti0;i4;i){intnxcur.xdir[i][0];intnycur.ydir[i][1];//在地图范围内没有访问过可通行if((nx1nxnny1nym)!visited[nx][ny]mp[nx][ny]!1){visited[nx][ny]true;node next{nx,ny};q.push(next);}}}}intmain(){cinnm;// n行m列的迷宫for(inti1;in;i){for(intj1;jm;j){cinmp[i][j];}}for(inti1;in;i){for(intj1;jm;j){if(!visited[i][j]mp[i][j]0){sxi;syj;bfs();//以(sx,sy)为起点搜索}}}coutcnt;return0;}/* 【输入用例2】 3 3 0 0 0 0 0 0 0 0 0 【输出用例2】 1 【输入用例3】 5 5 0 0 1 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 【输出用例3】 1 【输入用例4】 1 5 0 0 0 0 0 【输出用例4】 1 【输入用例5】 2 2 1 1 1 1 【输出用例5】 0 【输入用例6】 4 4 0 1 0 0 0 0 0 1 1 0 0 0 0 1 1 0 【输出用例6】 2 */快乐的马里奥【描述】马里奥是一个快乐的油漆工人这天他接到了一个油漆任务要求马里奥把一个 n 行 m 列的矩阵每一格都用油漆标记一个数字标记的顺序按照广度优先搜索的方式进行也就是他会按照如下方式标记1 、首先标记第 1 行第 1 列的单元格标记数字为 1 2 、然后标记当前单元格上下左右四个方向所有能标记的单元格且① 标记顺序按照右、下、左、上的优先级② 不能标记到矩阵外且标记过的数字不能重复标记3 、当本单元格标记结束寻找比本单元格中数字大 1 的单元格标记那个单元格的上下左右四个方向也是按照步骤 2 所示的要求进行标记。依次类推直到所有单元格都被标记。比如如果有一个3 * 3 的矩阵如下那么首先标记 1,1 单元格并按照上面步骤 2 的要求标记其四周能够标记的单元格标记结果如下接下来标记比 1,1 格大 1 的数字的四周的单元格也就是标记值为 2 的单元格四周的单元格标记结果如下1 2 31 1 22 33接下来标记值为 3 的单元格四周的单元格标记结果如下1 2 31 1 2 42 3 53接下来标记值为 4 的单元格四周的单元格标记结果如下1 2 31 1 2 42 3 53 6接下来标记值为 5 的单元格四周的单元格标记结果如下1 2 31 1 2 42 3 5 73 6 8接下来标记值为 6 的单元格四周的单元格但这个数字四周的单元格已经被标记因此继续标记值为7四周的单元格标记结果如下1 2 31 1 2 42 3 5 73 6 8 9此时发现标记结束得到如上图所示的标记结果。【输入描述】两个整数 n 和 m n 和 m 都是 3~100 之间的整数。【输出描述】输出 n 行 m 列的标记后的矩阵输出每个数后空一格【用例输入】3 3【用例输出】1 2 43 5 76 8 9#includeiostream#includevectorusingnamespacestd;intmain(){intn,m;cinnm;vectorvectorintmatrix(n,vectorint(m,0));inttotaln*m;vectorpairint,intpos(total1);// 存储每个数字的坐标索引从1到total// 初始化起点matrix[0][0]1;pos[1]{0,0};intmax_num1;// 按顺序处理每个数字k从1到totalfor(intk1;ktotal;k){intipos[k].first;intjpos[k].second;// 处理右方向i, j1intnii;intnjj1;if(ni0ninnj0njmmatrix[ni][nj]0){max_num;matrix[ni][nj]max_num;pos[max_num]{ni,nj};}// 处理下方向i1, jnii1;njj;if(ni0ninnj0njmmatrix[ni][nj]0){max_num;matrix[ni][nj]max_num;pos[max_num]{ni,nj};}// 处理左方向i, j-1nii;njj-1;if(ni0ninnj0njmmatrix[ni][nj]0){max_num;matrix[ni][nj]max_num;pos[max_num]{ni,nj};}// 处理上方向i-1, jnii-1;njj;if(ni0ninnj0njmmatrix[ni][nj]0){max_num;matrix[ni][nj]max_num;pos[max_num]{ni,nj};}}// 输出结果for(inti0;in;i){for(intj0;jm;j){coutmatrix[i][j] ;}coutendl;}return0;}/* 【输入用例2】 1 5 【输出用例2】 1 2 3 4 5 【输入用例3】 2 3 【输出用例3】 1 2 4 3 5 6 【输入用例4】 4 4 【输出用例4】 1 2 6 13 3 5 7 14 4 8 12 15 9 11 16 10 */人造星空【描述】A市利用无人机制造了一个nm大小的人造星空在这个nm大小的星空中每个点都有一个无人机无人机有发光和不发光两种不同的状态对于所有的发光点在空中就能形成独特的星空图形。图形中有多个不同的图案同一个图案的定义是这样的对于两个发光的点如果他们的曼哈顿距离对于A(x1,y1)和B(x2,y2)A和B之间的曼哈顿距离为|x1-x2||y1-y2|小于等于2那么这两个点就属于一个图案。请你编程计算一下这个n*m的图形中有多少个不同的图案。比如一个6 * 6的图形如下-#----##----–##–-#----–#-##该图形中有2个符合条件的图案-#----–#-##【输入描述】第一行两个数n和m。1n,m100接下来一共n行每行m个字符。对于第i行第j个字符如果其为“-”那么表示该点不发光如果其为“#”那么表示该点发光。不可能出现其他的字符。【输出描述】输出一个整数代表图案的个数。【用例输入】6 6-#----##----–##–-#----–#-##【用例输出】2#includeiostream#includevector#includequeueusingnamespacestd;intmain(){intn,m;// 网格的行数n和列数mcinnm;vectorstringgrid(n);// 存储网格数据的二维字符串数组每行是一个字符串for(inti0;in;i){cingrid[i];}// 初始化为全false所有格子初始未被访问vectorvectorboolvisited(n,vectorbool(m,false));intcount0;// 统计连通区域的数量最终输出结果// 曼哈顿距离|dx| |dy| 2例如横向移动2格、纵向移动1格等情况// 共12个方向覆盖了曼哈顿距离为1和2的所有可能方向intdirs[12][2]{{0,1},{0,-1},{0,2},{0,-2},// 横向移动列变化右1、左1、右2、左2{1,0},{-1,0},// 纵向移动行变化下1、上1{1,1},{1,-1},{-1,1},{-1,-1},// 对角线移动行和列各变化±1右下、右上、左下、左上{2,0},{-2,0}// 纵向长距离移动下2、上2};// 遍历网格中的每一个格子for(inti0;in;i){for(intj0;jm;j){// 如果当前格子是目标字符#且未被访问过说明发现新的连通区域if(grid[i][j]#!visited[i][j]){count;// 连通区域数量加1// 启动BFS遍历该连通区域的所有格子queuepairint,intq;// 队列存储待处理的格子坐标行, 列q.push(make_pair(i,j));// 将当前格子加入队列visited[i][j]true;// 标记当前格子为已访问// BFS循环处理队列中的所有格子直到队列为空while(!q.empty()){pairint,intpq.front();// 取出队列头部的格子q.pop();// 队首元素出队intxp.first;// 当前格子的行坐标intyp.second;// 当前格子的列坐标// 遍历所有12个方向的偏移量检查相邻格子for(intk0;k12;k){intdxdirs[k][0];// 当前方向的行偏移量上下移动intdydirs[k][1];// 当前方向的列偏移量左右移动intnxxdx;// 相邻格子的行坐标当前行偏移intnyydy;// 相邻格子的列坐标当前列偏移// 检查相邻格子是否在网格范围内不越界if(nx0nxnny0nym){// 如果相邻格子是目标字符#且未被访问过if(grid[nx][ny]#!visited[nx][ny]){visited[nx][ny]true;// 标记为已访问q.push(make_pair(nx,ny));// 加入队列继续BFS遍历}}}}}}}// 输出连通区域的总数coutcountendl;return0;}/* 【输入用例2】 3 3 --- -#- --- 【输出用例2】 1 【输入用例3】 1 5 #--#- 【输出用例3】 2 【输入用例4】 1 7 #-#-#-- 【输出用例4】 1 */泉水【描述】Leyni是一个地址调查员有一天在他调查的地方突然出现个泉眼。由于当地的地势不均匀有高有低他觉得如果这个泉眼不断的向外溶出水来这意味着这里在不久的将来将会一个小湖。水往低处流凡是比泉眼地势低或者等于的地方都会被水淹没地势高的地方水不会越过。而且又因为泉水比较弱当所有地势低的地方被淹没后水位将不会上涨一直定在跟泉眼一样的水位上。由于Leyni已经调查过当地很久了所以他手中有这里地势的详细数据。所有的地图都是一个矩形并按照坐标系分成了一个个小方格Leyni知道每个方格的具体高度。我们假定当水留到地图边界时不会留出地图外现在他想通过这些数据分析出将来这里将会出现一个多大面积的湖。【输入描述】有若干组数据每组数据的第一行有四个整数n,m,p1,p2(01000)n和m表示当前地图的长和宽p1和p2表示当前地图的泉眼位置即第p1行第p2列随后的n行中每行有m个数据。表示这每一个对应坐标的高度。【输出描述】输出对应地图中会有多少个格子被水充满。【用例输入】3 5 2 33 4 1 5 12 3 3 4 74 1 4 1 1【用例输出】6#includeiostream#includevector#includequeueusingnamespacestd;intmain(){// 读取多组测试数据直到输入结束intn,m,p1,p2;// n: 地图行数m: 地图列数p1: 泉眼行号1-basedp2: 泉眼列号1-basedwhile(cinnmp1p2){// 处理特殊情况地图行数或列数为0时直接输出0if(n0||m0){cout0endl;continue;// 跳过当前组数据处理下一组}// 定义二维数组存储地图高度n行m列vectorvectorintgrid(n,vectorint(m));// 读取每个格子的高度数据for(inti0;in;i){for(intj0;jm;j){cingrid[i][j];}}// 将泉眼的1-based坐标转换为0-based索引数组从0开始intxp1-1;// 泉眼的行索引intyp2-1;// 泉眼的列索引// 检查泉眼位置是否有效是否在地图范围内if(x0||xn||y0||ym){cout0endl;// 无效位置无淹没区域continue;// 跳过当前组数据}inthgrid[x][y];// 泉眼所在格子的高度水扩散的最高高度// 定义二维数组记录每个格子是否被访问过即是否被水淹没vectorvectorboolvisited(n,vectorbool(m,false));// 定义队列用于BFS遍历初始时将泉眼位置加入队列queuepairint,intq;q.push({x,y});// 泉眼入队visited[x][y]true;// 标记泉眼为已访问intcount1;// 计数器初始化为1泉眼本身已被淹没// 定义四个方向的偏移量上、下、左、右intdx[]{-1,1,0,0};// 行方向的偏移上-1行、下1行、左0行、右0行intdy[]{0,0,-1,1};// 列方向的偏移上0列、下0列、左-1列、右1列// BFS遍历从泉眼开始扩散直到队列为空while(!q.empty()){// 取出队列头部的当前格子坐标autocurq.front();q.pop();// 队首元素出队intcxcur.first;// 当前格子的行索引intcycur.second;// 当前格子的列索引// 检查当前格子的四个相邻方向上、下、左、右for(inti0;i4;i){// 计算相邻格子的坐标当前坐标方向偏移intnxcxdx[i];// 相邻格子的行索引intnycydy[i];// 相邻格子的列索引// 检查相邻格子是否满足以下条件// 1. 在地图范围内行索引0~n-1列索引0~m-1// 2. 未被访问过未被水淹没// 3. 高度小于等于泉眼高度会被水淹没if(nx0nxnny0nym){// 条件1有效范围if(!visited[nx][ny]grid[nx][ny]h){// 条件2和3未访问且高度符合visited[nx][ny]true;// 标记为已访问被淹没count;// 计数器加1新增淹没区域q.push({nx,ny});// 相邻格子入队继续扩散}}}}// 输出当前组数据中被水淹没的格子总数coutcountendl;}return0;}/* 【输入用例2】 1 1 1 1 5 【输出用例2】 1 【输入用例3】 2 4 1 2 4 3 1 2 1 2 2 5 【输出用例3】 6 【输入用例4】 3 3 2 2 5 5 5 5 2 1 5 1 1 【输出用例4】 4 */

C++广度优先搜索一（练习题）

相关推荐

RimWorld Mod开发实战：从零构建动态太阳能发电机

Windows摄像头无法检测——虚拟机USB配置导致

群晖NAS USB网卡驱动实战手册：3步免费解锁2.5G/5G/10G高速网络

更多资讯

GitHub Copilot CLI本地模型连接实战指南

开关电源11种拓扑选型指南：从原理到工程避坑

ARIMA模型在电力市场价格预测中的实践与优化

小学生学C++不是为了编程，而是训练逻辑思维

逆向解构引擎：把读文献变成拆论文，高效找研究缺口

RPA流程日志记录：设计原则与最佳实践

今日更新

淘宝商品详情API开发实战与性能优化指南

Unity Package Manager刷新错误排查与解决方案

Java record 规范构造器能否被反序列化或反射绕过

本周精选

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

本月热门

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

基于DRV8818与STM32的双极步进电机驱动方案实战解析

DRV8818PWPR+PIC18F45K80双极步进电机控制方案实战

读完文章，想聊聊您的网站？