【题解】【枚举】——First Step ファーストステップ
First Step (ファーストステップ)
题目背景
我们 Aqours，要第一次举办演唱会啦！
虽然学生会长看上去不怎么支持我们的样子，可是有了理事长的支持，我们还是被允许在校内的篮球场里歌唱！
歌曲也好好地准备过了，名字叫“最喜欢的话就没问题！ (ダイスキだったらダイジョウブ！)“，大家一定会喜欢的吧！
演唱会一定会顺利进行的！
希望不要发生停电什么的事故哦……！
题目描述
可是……这个篮球场，好像很久没有使用过的样子啊……
里面堆满了学校的各种杂物呢……
我们 Aqours 的成员要怎么在里面列队站下呢？
我们浦之星女子学院的篮球场是一个
R
R
R 行
C
C
C 列的矩阵，其中堆满了各种学校的杂物 (用 # 表示)，空地 (用 . 表示) 好像并不多的样子呢……
我们 Aqours 现在已经一共有 K K K 个队员了，要歌唱舞蹈起来的话，我们得排成一条 1 × K 1\times K 1×K 的直线，一个接一个地站在篮球场的空地上呢 (横竖均可)。
我们想知道一共有多少种可行的站位方式呢。
Aqours 的真正的粉丝的你，能帮我们算算吗？
输入格式
第一行三个整数 R , C , K R, C, K R,C,K。
接下来的 R R R 行 C C C 列，表示浦之星女子学院篮球场。
输出格式
总共的站位方式数量。
输入输出样例
输入 #1
5 5 2
.###.
##.#.
..#..
#..#.
#.###
输出 #1
8
提示
| R R R | C C C | K K K | 备注 | |
|---|---|---|---|---|
| 1 ∼ 2 1\sim2 1∼2 | ≤ 10 \leq 10 ≤10 | ≤ 10 \leq 10 ≤10 | ≤ min ( R , C ) \leq \min(R,C) ≤min(R,C) | 无 |
| 3 ∼ 4 3\sim4 3∼4 | ≤ 100 \leq 100 ≤100 | ≤ 100 \leq 100 ≤100 | ≤ 1 \leq 1 ≤1 | 无 |
| 5 ∼ 6 5\sim6 5∼6 | ≤ 100 \leq 100 ≤100 | ≤ 100 \leq 100 ≤100 | ≤ min ( R , C ) \leq \min(R,C) ≤min(R,C) | 没有障碍 |
| 7 ∼ 10 7\sim10 7∼10 | ≤ 100 \leq 100 ≤100 | ≤ 100 \leq 100 ≤100 | ≤ min ( R , C ) \leq \min(R,C) ≤min(R,C) | 无 |
对于所有数据， 1 ≤ R , C ≤ 100 1 \leq R,C \leq 100 1≤R,C≤100， 1 ≤ k ≤ min ( R , C ) 1 \leq k \leq \min(R,C) 1≤k≤min(R,C)。
1.思路解析
如果只能横着或只能竖着站，直接暴力枚举就行了。
但是这道题横竖均可，怎么办？那就分别枚举横着和竖着两种情况就行了。
我们先讨论横着站的情况。使用一个变量cnt来储存答案。
最外层的循环枚举每一行，如下：
for(int i=1;i<=R;i++)//首先枚举横着站的情况,i代表当前枚举的行数
{
}
第二重循环枚举每种可能的队头，即起点。注意最多枚举到C-K+1。
for(int i=1;i<=R;i++)//首先枚举横着站的情况,i代表当前枚举的行数
{
for(int j=1;j<=C-K+1;j++)//以第i行每一个可以作为起点的点j作为起点
{
}
}
接下来就是枚举后面的
K
K
K个位置了。首先定义一个变量is_can_stand，储存当前情况是否站的下，初始化为1。然后枚举后面的
K
K
K个位置，只要遇到障碍物#就跳出循环，并把is_can_stand设置为0。
for(int i=1;i<=R;i++)//首先枚举横着站的情况,i代表当前枚举的行数
{
for(int j=1;j<=C-K+1;j++)//以第i行每一个可以作为起点的点j作为起点
{
bool is_can_stand=1;//是否可以站下
for(int k=j;k<=K+j-1;k++)//分别枚举K个人站的位置
if(a[i][k]!='.')//如果不是空地
{
is_can_stand=0;
break;//不再判断以这个点为起点的可能性
}
if(is_can_stand)//统计答案
cnt++;
}
}
枚举竖着站和枚举横着站有异曲同工之妙，请读者自己尝试实现。
注意：当
K
=
1
K=1
K=1时，横着站和竖着站是一样的，此时需要答案/2。
本题解只讲述了一种适合萌新的做法，其实还有许多可以优化的地方。但因为
我懒篇幅关系，这里就不详细讲解了。
2.AC代码
#include<bits/stdc++.h>
using namespace std;
int R,C,K,cnt;//用cnt记录答案
char a[110][110];//储存篮球场地图
int main()
{
cin>>R>>C>>K;
for(int i=1;i<=R;i++)//读入地图
for(int j=1;j<=C;j++)
cin>>a[i][j];
for(int i=1;i<=R;i++)//首先枚举横着站的情况,i代表当前枚举的行数
{
for(int j=1;j<=C-K+1;j++)//以第i行每一个可以作为起点的点j作为起点
{
bool is_can_stand=1;//是否可以站下
for(int k=j;k<=K+j-1;k++)//分别枚举K个人站的位置
if(a[i][k]!='.')//如果不是空地
{
is_can_stand=0;
break;//不再判断以这个点为起点的可能性
}
if(is_can_stand)//统计答案
cnt++;
}
}
for(int i=1;i<=C;i++)//然后枚举竖着站的情况,i代表当前枚举的列数
{
for(int j=1;j<=R-K+1;j++)以第i列每一个可以作为起点的点j作为起点
{
bool is_can_stand=1;//是否可以站下
for(int k=j;k<=K+j-1;k++)//分别枚举K个人站的位置
if(a[k][i]!='.')//如果不是空地
{
is_can_stand=0;
break;//不再判断以这个点为起点的可能性
}
if(is_can_stand)//统计答案
cnt++;
}
}
(K==1)?cout<<cnt/2:cout<<cnt;
//如果只需要站一个人,那么横着站和竖着站计算了两次,需要除以2
return 0;
}
喜欢就订阅此专辑吧！
【蓝胖子编程教育简介】
蓝胖子编程教育，是一家面向青少年的编程教育平台。平台为全国青少年提供最专业的编程教育服务，包括提供最新最详细的编程相关资讯、最专业的竞赛指导、最合理的课程规划等。本平台利用趣味性和互动性强的教学方式，旨在激发孩子们对编程的兴趣，培养他们的逻辑思维能力和创造力，让孩子们在轻松愉快的氛围中掌握编程知识，为未来科技人才的培养奠定坚实基础。
欢迎扫码关注蓝胖子编程教育
