`
暴风雪
  • 浏览: 388002 次
  • 性别: Icon_minigender_2
  • 来自: 杭州
社区版块
存档分类
最新评论

Bayan 2015 Contest Warm Up C

 
阅读更多

在一块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;
}

 

0
0
分享到:
评论

相关推荐

    bayan-cms

    【标题】"bayan-cms" 是一个基于Strapi框架构建的内容管理系统(CMS)项目。Strapi是一款流行的开源Node.js内容管理框架,它允许开发者快速搭建自己的API后端,为Web应用提供数据支持。 【描述】"Strapi应用 您的...

    Circular-Mobile-Menu-for-bayan-blog:这个名字是不言自明的

    圆形-移动-菜单-for-bayan-blog 这个名字是不言自明的这是一个圆形菜单,可用于任何网站。 我个人在我的博客中使用它,但仅限于移动友好部分(700px 屏幕以下)。 在以下找到实时预览:

    Mac 网卡厂商对应列表2018最新

    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

    S4DS:BAYAN活动研讨会的讲义为“数据科学统计”

    数据科学统计从事数据科学项目需要一定的统计学基础。 此回购包含有关统计概念的入门资料。 它最初是由赞助的研讨会创建的。 由于人们对这种材料越来越感兴趣,因此我开始将其用于其他工作坊。软件和系统要求首选...

    omid-plus:Blog.ir中的响应式和改进版本的Omid模板

    注意:根据Bayan网站,此模板仅允许在Bayan博客中使用 若要使用,请将HTML文件放在当前模板的编辑部分中,并将CSS文件放在Blog.ir面板中当前模板CSS编辑部分中。 如果要使用模板中嵌入的社交媒体图标部分,请转到...

    设备mac与厂商对应

    - 地址:Phase 3, Bayan Lepas FIZ, Bayan Lepas Penang 11900 - 国家/地区:MY 3. **NETGEAR** - MAC地址:2C-30-33(十六进制表示法) - 厂商名称:NETGEAR - 地址:350 East Plumeria Drive, San Jose null...

    标准MAC与Vendor的对应关系

    - 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_app:mahe_ramdaan_app

    谷歌师兄的leetcode刷题笔记Mahe Ramdaan 应用程序 一个新的 Mahe Ramdaan 应用程序 帮助我们的穆斯林兄弟:person_light_skin_tone_beard:和姐妹们 :woman_with_headscarf: ...MP3、Bayan 等等 应用链接

    Emergency

    3-巴彦·阿布·哈吉(Bayan Abu Al-haj)。 4-Abdalrahman- Al-hmouz。 5-艾哈迈德·阿尔萨布格(Ahmad Alsabbag)。 6-Motaz abusaleh。 关于我们的项目: 至于我们的项目,这是一个方便找工作和工人的过程的...

    chocolate-pizza

    巧克力披萨 主要的 配对程序 巴彦·阿尔卡提卜(Bayan Alkhatib) 评论:这个HTML和CSS项目。 配对程序 巴彦Alkhatib Abdullah Alswallmeh 评论:这个HTML和CSS项目。 主要的

    利策科技:2021年半年度报告.PDF

    此外,4月,利策科技中标了马来西亚国家石油公司的海上Bayan油气田开发项目,负责MOPU平台的上部组块工艺模块交付,这是对公司技术积累和管理能力的高度认可。该项目预计在次年4月完成。 报告还提及了其他正在进行...

    代码201阅读笔记

    代码201阅读笔记 札记; 欢迎阅读笔记在这里,您可以找到有关HTML,CSS,JS的摘要。 作家: 化学工程师Bayan AL-khatib成为软件开发人员。 目录 # 班级 1个 2个 3 4 6 7 8 9 10 11 12 13 14 15

    Blog.ir font changer-crx插件

    语言:فارسی‎ 此扩展名可帮助用户在blog.ir(Blog Bayan)中更改管理员面板的字体。 该博客服务在面板中使用Tahoma字体。 借助扩展程序,您可以轻松地将其更改为Iran Sans字体。

    DS.rar_data structure_in

    在"DS.rar_data structure_in"这个压缩包中的"coddi bayan"可能就是关于这些概念的代码示例或练习题,通过实际编程来加深对二叉树的理解。 总之,二叉树作为数据结构的重要组成部分,其概念和操作是每个计算机科学...

    city_explorer_api

    实验室05 地标编号和名称:探索城市 预计完成时间:5小时 开始时间:2:50 pm ...作者:Bayan Khalil版本:1.0.0(如果在首次提交后进行了更多提交,请增加补丁/补丁的版本号) 概述 入门 建筑学 变更记录 -&gt;

    talab-2017:Ateneo TALAB网站

    Talakayang Alay Sa Bayan(TALAB)是在马尼拉雅典大学举行的全校活动。 该活动包括各种讲座,讲习班和小组讨论,旨在为学生提供一个反思国家面临的各种问题的机会。 该网站允许学生报名参加整个活动期间的课程。 该...

    读音

    我的名字叫Irbid的Anagheem Bayan,我拥有管理信息系统( MIS )的学士学位。 我想在网络开发中实现自我,发现梦想成真。 代码102阅读说明: 这是我创建的一些页面: 页数 链接 心态 降价促销 吉特 代码201阅读...

    About-me-project:这是关于“关于我-网页所有者-猜游戏”的仓库

    代码201 关于我的项目 巴彦·阿勒哈提卜 实验02: 评论: - lab-02 first lab for this project ; so 1/Mar is the date of creation of this repo. ... 航海家:巴彦·阿尔哈提卜(Bayan Alkhatib)

Global site tag (gtag.js) - Google Analytics