洛谷P3654 First Step题解
  vczFXvQp8ka5 2023年11月02日 48 0
C++

题目传送门

这是一道暴力枚举。

 


 

大致题意:R行C列的棋盘要放下长度为K的线段,“#”表示无法放置,问有多少种放置方法。

直接贴代码:

#include<bits/stdc++.h>
using namespace std;
int main(){
    string str;//读取字符串 
    int r,c,k,a[101][101],cnt=0;//数组a用来存储棋盘 
    cin>>r>>c>>k;//r表示行,c表示列,k表示线段长度 
    for(int i=1;i<=r;i++){
        cin>>str;//输入 
        for(int j=1;j<=c;j++){
            if(str[j-1]=='.')
            //将棋盘字符转为数值表示是否可以放置 
                a[i][j]=0;//0表示可以放置 
            else a[i][j]=1;//反之赋1不可放置 
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(a[i][j]==1||j+k-1>r)continue;
            //如果不可放置或无法容纳线段长度直接下一层循环 
            int flag=1;//标记是否有障碍物 
            if(a[i][j]==0){//可以放置 
                for(int l=j+1;l<j+k;l++){//枚举长度为k的线段 
                    if(a[i][l]==1){//从左往右枚举 
                        flag=0;//无法放置则标记为0 
                        break;//直接跳出循环 
                    }
                }
                if(flag==1)cnt++;//无障碍物,计数器+1 
            }
        }
    }
    for(int i=1;i<=r;i++){
        for(int j=1;j<=c;j++){
            if(a[i][j]==1||i+k-1>c)continue;
            //如果不可放置或无法容纳线段长度直接下一层循环 
            int flag=1;//标记是否有障碍物  
            if(a[i][j]==0){//可以放置 
            for(int l=i+1;l<i+k;l++){//枚举长度为k的线段
                if(a[l][j]==1){//从上往下枚举 
                    flag=0;//无法放置则标记为0 
                    break;//直接跳出循环 
                }
            }
            if(flag==1)cnt++;// 无障碍物,计数器+1 
            }    
        }
    }
    if(k==1)cout<<cnt/2;
    //特判,如果线段长度为1,横向纵向会判断两次,除以2输出 
    else cout<<cnt;
    return 0;
}

 

【版权声明】本文内容来自摩杜云社区用户原创、第三方投稿、转载,内容版权归原作者所有。本网站的目的在于传递更多信息,不拥有版权,亦不承担相应法律责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@moduyun.com

  1. 分享:
最后一次编辑于 2023年11月08日 0

暂无评论

推荐阅读
  8Tw5Riv1mGFK   2024年05月01日   80   0   0 C++
  BYaHC1OPAeY4   2024年05月08日   56   0   0 C++
  yZdUbUDB8h5t   2024年05月05日   43   0   0 C++
  oXKBKZoQY2lx   2024年05月17日   57   0   0 C++
vczFXvQp8ka5