openjudge_2.5基本算法之搜索_166:The Castle

题目

166:The Castle
总时间限制: 1000ms 内存限制: 65536kB
描述
在这里插入图片描述
Figure 1 shows the map of a castle.Write a program that calculates

  1. how many rooms the castle has
  2. how big the largest room is
    The castle is divided into m * n (m<=50, n<=50) square modules. Each such module can have between zero and four walls.
    输入
    Your program is to read from standard input. The first line contains the number of modules in the north-south direction and the number of modules in the east-west direction. In the following lines each module is described by a number (0 <= p <= 15). This number is the sum of: 1 (= wall to the west), 2 (= wall to the north), 4 (= wall to the east), 8 (= wall to the south). Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1. The castle always has at least two rooms.
    输出
    Your program is to write to standard output: First the number of rooms, then the area of the largest room (counted in modules).
    样例输入
    4
    7
    11 6 11 6 3 10 6
    7 9 6 13 5 15 5
    1 10 12 7 13 7 5
    13 11 10 8 10 12 13
    样例输出
    5
    9

翻译

在这里插入图片描述

图Figure1显示shows了一个城堡的地图。写一个计算calculates程序

  1. 城堡有多少个房间
  2. 最大的房间有多大啊
    城堡被划分为m * n (m<=50, n<=50)个正方形square单元modules。每个这样的模块可以有零到四面墙。

输入
您的程序将从标准输入中读取数据。
第一行包含南北方向的模块数和东西方向的模块数。
在接下来的几行中,每个模块用一个数字(0 <= p <= 15)来描述。
这个数字是以下数的总和:1(=西面的墙),2(=北面的墙),4(=东面的墙),8(=南面的墙)。
内壁被定义了两次;
模块1,1中向南的墙也表示为模块2,1中向北的墙。
城堡总是至少有两个房间。

输出
您的程序将写入标准输出:首先是房间的数量,然后是最大房间的面积(以模块计算)。

理解

1.逐个访问房间,没算进去就算一个。宽搜能到达的所有房间。
请添加图片描述

2.墙数和=1+2+4+8。有8就是有右墙,减掉后,看有没有4,以此类推。
3.往左,就要判断到达房间有没有右墙
往左是0,对于到达房间判断右墙2,
往上是1,对于到达房间判断下墙3
往右是2,对于到达房间判断左墙0
往下是3,对于到达房间判断上墙1 请添加图片描述

代码

#include <bits/stdc++.h>
using namespace std;
struct room{
bool w[5],//有无左上右下四堵墙
k;//该房间算了没
int x,y,//坐标
n,//该套房子房间数
id;//该房间是哪一套
void set(int d,int xx,int yx){
x=xx,y=yx;
k=0,n=1;
if(d>=8)w[3]=1,d-=8;//下
if(d>=4)w[2]=1,d-=4;//右
if(d>=2)w[1]=1,d-=2;//上
if(d>=1)w[0]=1,d-=1;//下
}
}r[55][55];
int m,n,//行列数
dx,//该房间墙数和
z,//共有几套放
maxd,//所有套间的最大房间数
d[4][2]={{0,-1},{-1,0},{0,1},{1,0}};//左上右下顺序算房间
queue q;//宽搜队列
bool ok(int f,int x,int y){
//确定该坐标有没有房间,算过没,0123左上右下该墙有没有
if(f<2)f+=2;else f-=2;//往左0去,到达房间就是判断右墙2;1,判断3;2判0,3是1
return x>=1&&x<=m&&y>=1&&y<=n&&!r[x][y].k&&!r[x][y].w[f];
}
void view(){
cout<<“房间”<<endl;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++)cout<<r[i][j].id<<“,”<<r[i][j].n<<“\t”;
cout<<endl;
}
}
int main(){
//freopen(“data.cpp”,“r”,stdin);
cin>>m>>n;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++){
cin>>dx;
r[i][j].set(dx,i,j);//确定有哪些墙
}
int x,y,
rn;//房间数
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)//遍历每个房间
if(!r[i][j].k){//没算过该房间
z++;rn=1;//套件总数增加,房间数从0开始
q.push(r[i][j]);r[i][j].k=1;r[i][j].id=z;
while(!q.empty()){
room rx=q.front();q.pop();
for(int di=0;di<4;di++){
x=rx.x+d[di][0],y=rx.y+d[di][1];
if(ok(di,x,y)){
r[x][y].k=1,r[x][y].n=++rn;
r[x][y].id=z;
maxd=max(maxd,rn);
q.push(r[x][y]);
}
}
}
//view();
}
cout<<z<<“\n”<<maxd<<endl;
return 0;
}

小结

队列,宽搜就能完成。
关键就是墙数和=1+2+4+8,得要拆解。
还有往左走,就得判断左边房间得右墙。

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

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

相关文章

Linux 内核学习(1) --- 时钟子系统

标题 时钟系统说明时钟树Clock Provider时钟通用数据结构clock_device 的注册clock_provider DTS配置和注册clock consumer时钟系统总结 时钟系统说明 时钟就是 SoC 中的脉搏&#xff0c;由它来控制各个部件按各自的节奏跳动。比如&#xff0c;CPU主频设置&#xff0c;串口的波…

切面条(蓝桥杯)

目录 题目 分析 代码实现 题目 一根高筋拉面&#xff0c;中间切一刀&#xff0c;可以得到2根面条。 如果先对折1次&#xff0c;中间切一刀&#xff0c;可以得到3根面条。 如果连续对折2次&#xff0c;中间切一刀&#xff0c;可以得到5根面条。 那么&#xff0c;连续对折1…

【报名指南】2023-2024学年AILD劳动技能大赛初赛报名流程

温馨提示&#xff1a; 1.AILD劳动技能大赛免费报名参赛。报名网址&#xff1a;aild.org.cn 2.报名时间即日起至5月31日。&#xff08;上海赛区线下挑战项目4月25日报名截止&#xff0c;线上挑战项目5月31日报名截止&#xff09;。 3.指导教师只能为行政备案学校的在职教师。…

C语言 数据输入输出

本文 我们来说 数据的输入与输出 及数据的运算 在程序的运算工程中 往往需要输入一些数据 而程序的运算 所得到的运算结果又需要输出给用户 因此 数据的输入与输出 就显得非常重要 在C语言中 不提供专门的输入输出语句 所有的输入输出 都是通过对标准库的调用 来实现的 一般 …

itop4412内核编译_编译自定义函数到内核

我的itop4412开发板是半路捡的&#xff0c;所以没办法加他们的售后群&#xff0c;遇到的问题只好一点点记录吧 内核驱动编译 在日常工作过程中&#xff0c;编写内核程序可能机会不多&#xff0c;但是将厂商提供的内核源码编译到固件中&#xff0c;这个技能还是必须掌握的。 i…

认识异常(1)

❤️❤️前言~&#x1f973;&#x1f389;&#x1f389;&#x1f389; hellohello~&#xff0c;大家好&#x1f495;&#x1f495;&#xff0c;这里是E绵绵呀✋✋ &#xff0c;如果觉得这篇文章还不错的话还请点赞❤️❤️收藏&#x1f49e; &#x1f49e; 关注&#x1f4a5;&a…

系统架构最佳实践 -- 一般优惠券平台系统架构设计

优惠券是商城的一种基础的营销工具&#xff0c;在目前c端用户对于电子优惠券已经非常熟悉的情况下&#xff0c;一般自营商城的营销活动系统&#xff0c;都是从优惠券开始搭建。 一、名词定义 基于个人理解&#xff0c;为方便表述&#xff0c;首先对可能产生歧义的名词进行如下…

十九.案例演示---天猫订单分析

目录 1.数据预处理 2.对订单状况进行分析 3.不同省份订单数详情 4.省份地图绘制 5.不同星期&#xff0c;订单分布 6.订单金额与订单数量 本次案例演示数据条数为:28010 import pandas as pd from pyecharts import options as optsdf_data pd.read_excel(../data/天猫订单…

【笔记】探索生成范式:大型语言模型在信息提取中的作用

探索生成范式&#xff1a;大型语言模型在信息提取中的作用 摘要介绍 &#x1f308;你好呀&#xff01;我是 是Yu欸 &#x1f30c; 2024每日百字篆刻时光&#xff0c;感谢你的陪伴与支持 ~ &#x1f680; 欢迎一起踏上探险之旅&#xff0c;挖掘无限可能&#xff0c;共同成长&am…

五、书架开发--3.弹出框功能开发、离线缓存功能开发

实现弹出框真实业务逻辑 私密阅读tab业务逻辑 1、根据点击的tab不同&#xff0c;从而展示出不同的popup弹窗 每个tab中都有自己的index&#xff0c;点击的时候获取这个index&#xff0c;就可以知道当前点击的是哪个tab&#xff0c;然后用switch-case来根据不同的index展示不…

【GD32】MQ-6丙烷检测传感器

2.34 MQ-6丙烷检测传感器 MQ-6气体传感器所使用的气敏材料是在清洁空气中电导率较低的二氧化锡(Sno2)。当传感器所处环境中存在可燃气体时&#xff0c;传感器的电导率随空气中可燃气体浓度的增加而增大。使用简单的电路即可将电导率的变化转换为该气体浓度相对应的输出信号。M…

Windows下使用PanguVip实现浮动IP

在某些高可用场景下&#xff0c;我们往往需要使用浮动IP来进行实际访问的切换&#xff0c;比如为了保证Web应用的高可用&#xff0c;当主节点宕机后&#xff0c;我们将浮动IP切换到备节点&#xff0c;那么备节点就继续可以提供服务&#xff0c;在linux下我们可以使用keepalived…

scala---基础核心知识

一、什么是scala Scala 是一种多范式的编程语言&#xff0c;其设计初衷是要集成面向对象编程和函数式编程的各种特性。Scala运行于Java平台&#xff08;Java虚拟机&#xff09;&#xff0c;并兼容现有的Java程序。 二、为什么要学习scala 1、优雅 2、速度快 3、能融合到hado…

【SpringBoot】获取参数

获取参数 传递单个参数传递多个参数传递对象后端参数重命名传递数组传递 json 数据获取 URL 中参数上传文件获取 cookie 和 session获取cookie获取session 传递单个参数 RequestMapping("/user") RestController public class UserController {// 传递单个参数Reque…

【Delphi 爬虫库 1】GET和POST方法

文章目录 1.最简单的Get方法实现2.可自定义请求头、自定义Cookie的Get方法实现3.提取响应协议头4.实现Post请求完成单词翻译 爬虫的基本原理是根据需求获取信息并返回。就像当我们感到饥饿时&#xff0c;可以选择自己烹饪食物、外出就餐&#xff0c;或者订外卖一样。在编程中&a…

Linux之bpfjit(2)使用分析和mini-tcpdump实现

Linux之bpfjit(2)使用分析和mini-tcpdump实现 Author: Once Day Date: 2024年4月13日 一位热衷于Linux学习和开发的菜鸟&#xff0c;试图谱写一场冒险之旅&#xff0c;也许终点只是一场白日梦… 漫漫长路&#xff0c;有人对你微笑过嘛… 全系列文章可以参考专栏&#xff1a;…

纯纯python实现梯度下降、随机梯度下降

最近面试有要求手撕SGD&#xff0c;这里顺便就把梯度下降、随机梯度下降、批次梯度下降给写出来了 有几个注意点&#xff1a; 1.求梯度时注意label[i]和pred[i]不要搞反&#xff0c;否则会导致模型发散 2.如果跑了几千个epoch&#xff0c;还是没有收敛&#xff0c;可能是学习率…

Linux 秋招必知必会(三、线程、线程同步)

六、线程 38. 什么是线程 线程是参与系统调度的最小单位&#xff0c;它被包含在进程之中&#xff0c;是进程中的实际运行单位 一个进程中可以创建多个线程&#xff0c;多个线程实现并发运行&#xff0c;每个线程执行不同的任务 主线程&#xff1a;当一个程序启动时&#xff0…

【Qt 学习笔记】Qt控件概述

博客主页&#xff1a;Duck Bro 博客主页系列专栏&#xff1a;Qt 专栏关注博主&#xff0c;后期持续更新系列文章如果有错误感谢请大家批评指出&#xff0c;及时修改感谢大家点赞&#x1f44d;收藏⭐评论✍ Qt控件概述 文章编号&#xff1a;Qt 学习笔记 / 14 文章目录 Qt控件概…

排序之快速排序

代码 class Solution {public int[] sortArray(int[] nums) {merge(nums, 0, nums.length - 1);return nums;}private void merge(int[] nums, int l, int r){if(l > r) return;// 随机选取主元int i new Random().nextInt(r - l 1) l;int temp nums[i];nums[i] nums[…