ABC337

Table of Contents

  1. D - Cheating Gomoku Narabe
    1. コード

D - Cheating Gomoku Narabe

D - Cheating Gomoku Narabe

入力は表形式ですが、行ごと列ごとに独立して考えることができます。例えば、k=3 のときの以下の表について考えてみます。

1
2
3
xo.x..o.
..o.xxxx
xx.oxxxx

２ 行目の xo.x..o. を xo.xooo. や xo.x.ooo にすることで条件を満たしますが（操作回数は 2 回）、このとき 2 行目以外のデータには依存しません。列方向について考えるときも同様です。よって、すべての行とすべての列について操作回数を求め、最小の操作回数が答えとなります。

続いて、どのように操作回数を求めるかを考えます。操作回数は長さ K の文字列に含まれる . の数によって決まります。ただし、x を含んではならない。ここでは累積和を使います。

. の出現回数の累積和と x の出現回数の累積和をそれぞれ求め、 x の出現回数が 0 回の範囲の . の出現回数が操作回数です。

0 1 2 3 4 5 6 7 8
x o . x . . o .
ng_sum 0 1 1 1 2 2 2 2 2
dot_sum 0 0 0 1 1 2 3 3 4

例えば、末尾の .o. は x の出現回数が 0 回 (ng_sum[8]-ng_sum[5]) で、. の出現回数が 2 回 (dot_sum[8]-dot_sum[5]) なので操作回数は 2 回です。

コード

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <string>
#include <vector>
#include <climits>
using namespace std;

int check_row(vector<vector<char>> &board, int w, int k, int i)
{
    vector<int> dot_sum(w + 1);
    vector<int> ng_sum(w + 1);
    for (int j = 0; j < w; j++)
    {
        dot_sum[j + 1] = dot_sum[j];
        if (board[i][j] == '.')
        {
            dot_sum[j + 1]++;
        }

        ng_sum[j + 1] = ng_sum[j];
        if (board[i][j] == 'x')
        {
            ng_sum[j + 1]++;
        }
    }

    int result = INT_MAX;
    for (int j = k; j <= w; j++)
    {
        int num_ng = ng_sum[j] - ng_sum[j - k];
        if (num_ng == 0)
        {
            int num_dot = dot_sum[j] - dot_sum[j - k];
            result = min(result, num_dot);
        }
    }
    return result;
}

int check_col(vector<vector<char>> &board, int h, int k, int j)
{
    vector<int> dot_sum(h + 1);
    vector<int> ng_sum(h + 1);
    for (int i = 0; i < h; i++)
    {
        dot_sum[i + 1] = dot_sum[i];
        if (board[i][j] == 'o')
        {
            dot_sum[i + 1]++;
        }

        ng_sum[i + 1] = ng_sum[i];
        if (board[i][j] == 'x')
        {
            ng_sum[i + 1]++;
        }
    }

    int result = INT_MAX;
    for (int i = k; i <= h; i++)
    {
        int num_ng = ng_sum[i] - ng_sum[i - k];
        if (num_ng == 0)
        {
            int num_dot = dot_sum[i] - dot_sum[i - k];
            result = min(result, k - num_dot);
        }
    }
    return result;
}

int main()
{
    int h, w, k;
    cin >> h >> w >> k;
    vector<vector<char>> board(h, vector<char>(w));
    for (int i = 0; i < h; i++)
    {
        for (int j = 0; j < w; j++)
        {
            cin >> board[i][j];
        }
    }

    int answer = INT_MAX;
    for (int i = 0; i < h; i++)
    {
        answer = min(answer, check_row(board, w, k, i));
    }
    for (int j = 0; j < w; j++)
    {
        answer = min(answer, check_col(board, h, k, j));
    }

    if (answer == INT_MAX)
    {
        cout << -1 << endl;
    }
    else
    {
        cout << answer << endl;
    }

    return 0;
}