P3654. First Step

发表于 分类于 阅读次数： Waline： 本文字数： 213 阅读时长 ≈ 1 分钟

考点

  • 枚举

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <bits/stdc++.h>

using namespace std;

char arr[101][101];

int R, C, K, ans = 0;

int walk[2][2] = {{0, 1}, {1, 0}};

void cnt(int x, int y, int idx)
{
    int res = 0;
    while (x <= R && y <= C && arr[x][y] == '.' && res < K)
    {
        x += walk[idx][0], y += walk[idx][1];
        ++res;
    }
    if (res == K)
        ++ans;
}

int main()
{
    cin >> R >> C >> K;
    for (int i = 1; i <= R; ++i)
        for (int j = 1; j <= C; ++j)
            cin >> arr[i][j];
    for (int i = 1; i <= R; ++i)
        for (int j = 1; j <= C; ++j)
            cnt(i, j, 0), cnt(i, j, 1);
    // K等于1的时候会重复
    cout << (K == 1 ? ans >> 1 : ans);
    return 0;
}

思路

枚举所有点，每次判断从当前位置向右走或向下走是否满足连续K个空位即可（向右走和向下走可以保证情况不重复）

坑点在于，当K等于1时结果要除2，因为此时向右和向下走情况是重复的