【题目来源】
洛谷：P3654 First Step (ファーストステップ) - 洛谷 (luogu.com.cn)
【题目描述】
我们 Aqours，要第一次举办演唱会啦！
虽然学生会长看上去不怎么支持我们的样子，可是有了理事长的支持，我们还是被允许在校内的篮球场里歌唱！
歌曲也好好地准备过了，名字叫“最喜欢的话就没问题！ (ダイスキだったらダイジョウブ！)“，大家一定会喜欢的吧！
演唱会一定会顺利进行的！
希望不要发生停电什么的事故哦……！
可是……这个篮球场，好像很久没有使用过的样子啊……
里面堆满了学校的各种杂物呢……
我们 Aqours 的成员要怎么在里面列队站下呢？
我们浦之星女子学院的篮球场是一个 \(R\) 行 \(C\) 列的矩阵，其中堆满了各种学校的杂物 (用 # 表示)，空地 (用 . 表示) 好像并不多的样子呢……
我们 Aqours 现在已经一共有 \(K\) 个队员了，要歌唱舞蹈起来的话，我们得排成一条 \(1\times K\) 的直线，一个接一个地站在篮球场的空地上呢 (横竖均可)。
我们想知道一共有多少种可行的站位方式呢。
Aqours 的真正的粉丝的你，能帮我们算算吗？
【输入】
第一行三个整数 \(R,C,K\)。
接下来的 \(R\) 行 \(C\) 列，表示浦之星女子学院篮球场。
【输出】
总共的站位方式数量。
【输入样例】
5 5 2
.###.
##.#.
..#..
#..#.
#.###
【输出样例】
8
【解题思路】
【算法标签】
《洛谷 P3654 First Step》 #模拟# #枚举# #洛谷月赛#
【代码详解】
#include <bits/stdc++.h>
using namespace std;int r, c, k; // 行数、列数、连续格子数k
int a[105][105] = {0}; // 存储网格，1表示空地，0表示障碍
int ans = 0, sum = 0; // ans: 有效放置数，sum: 空地总数// 检查水平方向是否可以放置
bool search1(int x, int y)
{if (y + k - 1 > c) return false; // 超出列边界for (int i = y; i < y + k; i++) if (a[x][i] == 0) return false; // 遇到障碍return true;
}// 检查垂直方向是否可以放置
bool search2(int x, int y)
{if (x + k - 1 > r) return false; // 超出行边界for (int i = x; i < x + k; i++) if (a[i][y] == 0) return false; // 遇到障碍return true;
}int main() {char tmp;cin >> r >> c >> k;// 读取网格数据并统计空地总数for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) {cin >> tmp;if (tmp == '.') {a[i][j] = 1;sum++;}}// 特殊处理k=1的情况if (k == 1) {cout << sum; // 每个空地都是有效放置return 0;}// 检查每个空地作为起点的水平和垂直方向for (int i = 1; i <= r; i++) for (int j = 1; j <= c; j++) if (a[i][j] == 1) { // 如果是空地if (search1(i, j)) ans++; // 检查水平方向if (search2(i, j)) ans++; // 检查垂直方向}cout << ans;return 0;
}
【运行结果】
5 5 2
.###.
##.#.
..#..
#..#.
#.###
8