It takes two (搜索)

本题链接:登录—专业IT笔试面试备考平台_牛客网

题目:

样例:

输入
3 4
AAAO
AAAA
AAAA

输出
NO

思路:

        根据题目意思,如果存在的 A 联通不可以成为 矩形,输出 NO,否则输出 YES

        这道题看数据范围是 1000 的图,所以可以联想到搜索。

        对于 ‘ 感染类 ’ 的搜索,BFS最直观合适。

        其中一个核心点就是如何知道右下角的坐标。

        当搜索寻找矩形的时候,我们找到相应的右下角坐标,随后统计搜索的面积与右下角坐标和左上角坐标相乘的面积,是否一致,如果一致,则是矩形,反之。

        我们可以注意到,右下角的坐标永远比坐上角的坐标大,即  右下角(x,y) > 左上角(x,y)

        所以我们每次取 坐标的最大值即可。

        // 寻找右下角lx = max(lx,now.x);ly = max(ly,now.y);

代码详解如下:

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define umap unordered_map
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e6 + 10;
inline void solve();
signed main()
{
//	freopen("a.txt", "r", stdin);IOS;int _t = 1;
// 	cin >> _t;while (_t--){solve();}return 0;
}bool st[1010][1010];
string g[N];
int n,m;
using PII = pair<int,int>;
int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};// 判断是否可进一步搜索
inline bool isRun(int x,int y)
{return (x >= 0 and x < n and y >= 0 and y < m and !st[x][y] and g[x][y] == 'A');
} // BFS 搜索
inline bool BFS(int x,int y)
{queue<PII>q;q.emplace(PII(x,y));int sum = 0; // 记录搜索面积int lx = -1,ly = -1;	// 记录右下角坐标while(q.size()){PII now = q.front();q.pop();++sum;	// 统计搜索到的面积// 寻找右下角lx = max(lx,now.x);ly = max(ly,now.y);st[now.x][now.y] = true;for(int i = 0;i < 4;++i){int bx = now.x + dx[i];int by = now.y + dy[i];if(isRun(bx,by)){q.emplace(PII(bx,by));st[bx][by] = true;}}}// 计算右下角坐标和左上角坐标形成的矩形面积int t = (lx - x + 1)*(ly - y + 1);// 判断是否与搜索面积相等return (t != sum);
}inline void solve()
{cin >> n >> m;for(int i = 0;i < n;++i) cin >> g[i];for(int i = 0;i < n;++i){for(int j = 0;j < m;++j){if(!st[i][j] and g[i][j] == 'A'){if(BFS(i,j)){cout << "NO" << endl;return ;}}}}cout << "YES" << endl;
}

最后提交:

        

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

windwos权限维持

1.php 不死马权限维持 <?php ignore_user_abort(); //关掉浏览器&#xff0c;PHP脚本也可以继续执行. set_time_limit(0);//通过set_time_limit(0)可以让程序无限制的执行下去 $interval 5; // 每隔*秒运行 do { $filename test.php; if(file_exists($filename)) { echo…

你是工作了十年,还是工作一年,重复了十遍?

你是工作了十年&#xff0c;还是工作一年&#xff0c;重复了十遍&#xff1f; 很多人刻舟求剑、画地为牢&#xff0c;就是缺少复盘意识。 没有复盘&#xff0c;没有进步。这是来自 B 站 Up 主檀东东Tango的复盘四步法&#xff1a; &#x1f449; https://www.bilibili.com/v…

Leaflet 中创建一个二维地图

要在 Leaflet 中创建一个二维地图&#xff0c;需要以下步骤&#xff1a; 1. 引入 Leaflet 库 首先&#xff0c;你需要在 HTML 文件中引入 Leaflet 库的 CSS 和 JavaScript 文件。你可以从官方网站下载 Leaflet&#xff0c;或者通过 CDN 引入。 <!-- Leaflet CSS --> &…

uni-app中web-view的使用

1. uni-app中web-view的使用 uni-app中的web-view是一个 web 浏览器组件&#xff0c;可以用来承载网页的容器&#xff0c;uni-app开发的app与web-view实现交互的方式相关简单&#xff0c;应用通过属性message绑定触发事件&#xff0c;然后在web-view的网页向应用 postMessage 触…

高防服务器、高防IP、高防CDN的工作原理是什么

高防IP高防CDN我们先科普一下是什么是高防。“高防”&#xff0c;顾名思义&#xff0c;就犹如网络上加了类似像盾牌一样很高的防御&#xff0c;主要是指IDC领域的IDC机房或者线路有防御DDOS能力。 高防服务器主要是比普通服务器多了防御服务&#xff0c;一般都是在机房出口架设…

智能算法-遗传算法 学习笔记

适应度的计算可类别为神经网络的目标函数&#xff0c;但此算法属于无监督学习&#xff0c;宏观来讲为搜寻最优解&#xff08;梯度&#xff09;的方式不同&#xff1f; 但神经网络中好像并不存在变异操作&#xff08;参数矩阵突变&#xff09;&#xff1f; 交叉的话残差网络ResN…

文件夹无法压缩是怎么回事?很简单的一个小原因~

电脑为什么显示没法压缩了&#xff0c;明明后台没有打开文件&#xff0c;却提示另一个程序正在使用文件&#xff0c;无法访问&#xff0c;压缩失败。 通常这种情况是因为后台有程序正在读取你准备压缩的文件&#xff0c;例如使用wps和office修改了word、excel、ppt等文件还未保…

OpenHarmony实战开发-Web组件的使用

介绍 本篇Codelab使用ArkTS语言实现一个简单的免登录过程&#xff0c;向大家介绍基本的cookie管理操作。主要包含以下功能&#xff1a; 获取指定url对应的cookie的值。设置cookie。清除所有cookie。免登录访问账户中心。 原理说明 本应用旨在说明Web组件中cookie的管理操作。…

第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数

解题思路&#xff1a; 快速幂 欧拉函数 快速幂比较常见于数据较大的取模场景&#xff0c;欧拉函数感觉还是有点抽象 注意&#xff1a; 取模的时候就不要简写了&#xff0c;例如&#xff1a;res res * a % mod;不要写成res * a % mod; import java.util.Scanner;public c…

C++判断点是否在三角形内部

1.问题 判断点是否在三角形内部。 2.思路 计算向量AB和AP的叉积、向量BC和BP的叉积、向量CA和CP的叉积&#xff0c;如果所有的叉积符号相同&#xff0c;则点在三角形内部。 3.代码实现和注释 #include <iostream> #include <vector>// 计算两个二维向量的叉积 …

蚂蚁庄园今日答案

蚂蚁庄园是一款爱心公益游戏&#xff0c;用户可以通过喂养小鸡&#xff0c;产生鸡蛋&#xff0c;并通过捐赠鸡蛋参与公益项目。用户每日完成答题就可以领取鸡饲料&#xff0c;使用鸡饲料喂鸡之后&#xff0c;会可以获得鸡蛋&#xff0c;可以通过鸡蛋来进行爱心捐赠。其中&#…

基于JSP的辅导员工作管理系统

基于JSP的辅导员工作管理系统的设计与实现 摘要 在这个大时代信息化的背景之下&#xff0c;涌现了许多的信息化的管理模式&#xff0c;形成了这个大时代背景下的独有的管理的形式和独具特色的管理的类型和模式。其中就包括信息化的员工工作的管理模式。现在越来越多的人们接受…

电商打单ERP必备API列表-API调用指南

1、打开淘宝开放平台API文档&#xff0c;查看API参数。 2、选择需要的API&#xff0c;进行测试对接。注册账号获取APIkey 3、进入API测试页&#xff0c;开始测试taobao.custom custom-自定义API操作 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方…

Redis命令介绍

一、redis启动&#xff1a; 本地启动&#xff1a;redis-cli 远程启动&#xff1a;redis-cli -h host -p port -a password Redis 连接命令 1 AUTH password 验证密码是否正确 2 ECHO message 打印字符串 3 PING 查看服务是否运行 4 QUIT 关闭当前连接 5 SELECT index 切换…

如何用磁力仪探测管缆的位置和埋深?

不论是航空磁测&#xff0c;还是海洋磁测&#xff0c;都是直接测量磁场总强度T&#xff0c;而后以总磁异常ΔT成图。磁异常总强度Ta是磁场总强度T与正常场T0的矢量差&#xff0c;即&#xff1a; Ta&#xff1d; T&#xff0d; T0 根据参考文献1&#xff0c;2的推导&#xff0c…

c++红黑树

c红黑树 1. 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍&…

Qt消息机制和事件

Qt消息机制和事件 Qt消息机制和事件--2 事件 事件&#xff08;event&#xff09;是由系统或者 Qt 本身在不同的时刻发出的。当用户按下鼠标、敲下键盘&#xff0c;或者是窗口需要重新绘制的时候&#xff0c;都会发出一个相应的事件。一些事件在对用户操作做出响应时发出&…

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言…

【Java程序设计】【C00415】基于(JavaWeb)Springboot的家教管理系统(含论文)

基于&#xff08;JavaWeb&#xff09;Springboot的家教管理系统&#xff08;含论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#xff0c;开发过上千…

07、Lua 流程控制

Lua 流程控制 Lua 流程控制控制结构语句 Lua 流程控制 Lua编程语言流程控制语句通过程序设定一个或多个条件语句来设定。在条件为 true 时执行指定程序代码&#xff0c;在条件为 false 时执行其他指定代码。 以下是典型的流程控制流程图&#xff1a; 控制结构的条件表达式结…