在一块n*m的区域中有一块a*b的刷子,这块刷子只能向下or向右,扫过的区域为x
给出一块区域,问这个区域是否可以由某块刷子刷成,如果可以输出刷子最小面积,不可以则输出-1
思路:
暴力枚举刷子的边长并验证,输出最小的刷子面积。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; char str[1002][1002]; int n,m,ssa,ssb,sum,dpa[1002][1002],dpb[1002][1002],dp[1002][1002]; bool right(int loca,int locb,int lena,int lenb){ if(locb+lenb-1>m)return 0; if(dpa[loca+lena-1][locb+lenb]-dpa[loca-1][locb+lenb]!=lena)return 0; return 1; } bool down(int loca,int locb,int lena,int lenb){ if(loca+lena-1>n)return 0; if(dpb[loca+lena][locb+lenb-1]-dpb[loca+lena][locb-1]!=lenb)return 0; return 1; } bool check(int lena,int lenb){ int loca=ssa,locb=ssb,i,j; if(ssa+lena-1>n||ssb+lenb-1>m)return 0; if(dp[loca+lena-1][locb+lenb-1]-dp[loca-1][locb+lenb-1]-dp[loca+lena-1][locb-1]+dp[loca-1][locb-1]!=lena*lenb)return 0; sum-=lena*lenb; while(1){ bool flagr=0,flagl=0; if(right(loca,locb,lena,lenb))flagr=1; if(down(loca,locb,lena,lenb))flagl=1; if(flagl&&flagr){ return 0; } if(!flagl&&!flagr){ break; } if(flagr){ sum-=lena; locb++; } if(flagl){ sum-=lenb; loca++; } } if(sum!=0)return 0; return 1; } int main(){ int i,j,k,tot; while(cin>>n>>m){ for(i=1;i<=n;i++){ cin>>str[i]+1; } if(n==1&&m==1){ cout<<1<<endl; continue; } tot=0; bool flag=0; memset(dp,0,sizeof(dp)); memset(dpa,0,sizeof(dpa)); memset(dpb,0,sizeof(dpb)); for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]; if(str[i][j]=='X'){ if(!flag)ssa=i,ssb=j; flag=1; tot++; dp[i][j]++; dpa[i][j]=dpa[i-1][j]+1; dpb[i][j]=dpb[i][j-1]+1; } } } flag=0; int res=n*m; for(i=1;i<=n;i++){ for(j=1;j<=m;j++){ if(i*j>=res)continue; sum=tot; if(check(i,j)){ flag=1; res=i*j; } } } if(!flag)cout<<-1<<endl; else cout<<res<<endl; } return 0; }
相关推荐
【标题】"bayan-cms" 是一个基于Strapi框架构建的内容管理系统(CMS)项目。Strapi是一款流行的开源Node.js内容管理框架,它允许开发者快速搭建自己的API后端,为Web应用提供数据支持。 【描述】"Strapi应用 您的...
圆形-移动-菜单-for-bayan-blog 这个名字是不言自明的这是一个圆形菜单,可用于任何网站。 我个人在我的博客中使用它,但仅限于移动友好部分(700px 屏幕以下)。 在以下找到实时预览:
Mac 网卡厂商对应列表2018最新,25716条 例: E0-43-DB (hex) Shenzhen ViewAt Technology Co.,Ltd. E043DB (base 16) Shenzhen ViewAt Technology Co.,... Phase 3, Bayan Lepas FIZ Bayan Lepas Penang 11900 MY
数据科学统计从事数据科学项目需要一定的统计学基础。 此回购包含有关统计概念的入门资料。 它最初是由赞助的研讨会创建的。 由于人们对这种材料越来越感兴趣,因此我开始将其用于其他工作坊。软件和系统要求首选...
注意:根据Bayan网站,此模板仅允许在Bayan博客中使用 若要使用,请将HTML文件放在当前模板的编辑部分中,并将CSS文件放在Blog.ir面板中当前模板CSS编辑部分中。 如果要使用模板中嵌入的社交媒体图标部分,请转到...
- 地址:Phase 3, Bayan Lepas FIZ, Bayan Lepas Penang 11900 - 国家/地区:MY 3. **NETGEAR** - MAC地址:2C-30-33(十六进制表示法) - 厂商名称:NETGEAR - 地址:350 East Plumeria Drive, San Jose null...
- Address: Phase 3, Bayan Lepas FIZ, Bayan Lepas Penang 11900 - Country: MY 3. **NETGEAR** - MAC Address: 2C:30:33 (Hex) 或 2C3033 (Base16) - Address: 350 East Plumeria Drive, San Jose null 95134...
巴彦·阿尔哈提卜(Bayan Alkhatib) 关于我: 我是约旦大学的bayan alkhatib化学工程师,在参加本课程之前,我已经工作了6个月。 表中的内容
谷歌师兄的leetcode刷题笔记Mahe Ramdaan 应用程序 一个新的 Mahe Ramdaan 应用程序 帮助我们的穆斯林兄弟:person_light_skin_tone_beard:和姐妹们 :woman_with_headscarf: ...MP3、Bayan 等等 应用链接
3-巴彦·阿布·哈吉(Bayan Abu Al-haj)。 4-Abdalrahman- Al-hmouz。 5-艾哈迈德·阿尔萨布格(Ahmad Alsabbag)。 6-Motaz abusaleh。 关于我们的项目: 至于我们的项目,这是一个方便找工作和工人的过程的...
巧克力披萨 主要的 配对程序 巴彦·阿尔卡提卜(Bayan Alkhatib) 评论:这个HTML和CSS项目。 配对程序 巴彦Alkhatib Abdullah Alswallmeh 评论:这个HTML和CSS项目。 主要的
此外,4月,利策科技中标了马来西亚国家石油公司的海上Bayan油气田开发项目,负责MOPU平台的上部组块工艺模块交付,这是对公司技术积累和管理能力的高度认可。该项目预计在次年4月完成。 报告还提及了其他正在进行...
代码201阅读笔记 札记; 欢迎阅读笔记在这里,您可以找到有关HTML,CSS,JS的摘要。 作家: 化学工程师Bayan AL-khatib成为软件开发人员。 目录 # 班级 1个 2个 3 4 6 7 8 9 10 11 12 13 14 15
语言:فارسی 此扩展名可帮助用户在blog.ir(Blog Bayan)中更改管理员面板的字体。 该博客服务在面板中使用Tahoma字体。 借助扩展程序,您可以轻松地将其更改为Iran Sans字体。
在"DS.rar_data structure_in"这个压缩包中的"coddi bayan"可能就是关于这些概念的代码示例或练习题,通过实际编程来加深对二叉树的理解。 总之,二叉树作为数据结构的重要组成部分,其概念和操作是每个计算机科学...
实验室05 地标编号和名称:探索城市 预计完成时间:5小时 开始时间:2:50 pm ...作者:Bayan Khalil版本:1.0.0(如果在首次提交后进行了更多提交,请增加补丁/补丁的版本号) 概述 入门 建筑学 变更记录 ->
Talakayang Alay Sa Bayan(TALAB)是在马尼拉雅典大学举行的全校活动。 该活动包括各种讲座,讲习班和小组讨论,旨在为学生提供一个反思国家面临的各种问题的机会。 该网站允许学生报名参加整个活动期间的课程。 该...
我的名字叫Irbid的Anagheem Bayan,我拥有管理信息系统( MIS )的学士学位。 我想在网络开发中实现自我,发现梦想成真。 代码102阅读说明: 这是我创建的一些页面: 页数 链接 心态 降价促销 吉特 代码201阅读...
代码201 关于我的项目 巴彦·阿勒哈提卜 实验02: 评论: - lab-02 first lab for this project ; so 1/Mar is the date of creation of this repo. ... 航海家:巴彦·阿尔哈提卜(Bayan Alkhatib)