Mujin Programming Challenge 2018 C - 右折

問題概要

C - 右折

解法

鉛直方向を$i$、横方向を$j$とします。全「.」マスから探索を行っていては間に合いそうになく、またそれを効率的に解くのも簡単ではなさそうなので、右折する点を決め打ちしてみます。

上図のようなフィールドで、マス(2, 2)で右折する場合を考えてみます。この点で右折するパターンは図に示した

左側から侵入して右折するパターン(青)
下側から侵入して右折するパターン(黄色)
右側から侵入して右折するパターン(ピンク)
上側から侵入して右折するパターン(緑)

の4パターンになります。

いま、マス$(i, j)$から上下左右それぞれの方向に連続している「.」の個数をそれぞれ$u_{ij}$、$d_{ij}$、$l_{ij}$、$r_{ij}$、とすると、

左側から侵入して右折するパターンの順序対の個数 : $l_{ij} \times d_{ij}$
下側から侵入して右折するパターンの順序対の個数 : $d_{ij} \times r_{ij}$
右側から侵入して右折するパターンの順序対の個数 : $u_{ij} \times r_{ij}$
上側から侵入して右折するパターンの順序対の個数 : $u_{ij} \times l_{ij}$

となるので、マス$(i, j)$で右折する全パターンの順序対の個数$p_{ij}$は$l_{ij} \times d_{ij} + d_{ij} \times r_{ij} + u_{ij} \times r_{ij} + u_{ij} \times l_{ij} = (u_{ij} + d_{ij})(l_{ij} + r_{ij})$となります。
よって、全ての「.」マスに対してこの計算を行い、それらを足し上げれば求める答えになります。

各「.」マスから上下左右に連続する「.」の個数を求める際、各マスから深さ優先探索的に(「#」にぶつかるまで)求めようとするとTLEしてしまいますが、これは、各行（列）で累積和的に「.」の個数を左右（上下）それぞれで数えていけば良いです。

ソースコード

# include <bits/stdc++.h>

using namespace std;

# define llong long long int
# define ldouble long double
# define fore(i, x) for (auto &i : n)
# define rep(i, n) for (int i = 0; i < n; ++i)
# define repr(i, n) for (int i = n; i >= 0; --i)
# define stl_rep(itr, x) for (auto itr = x.begin(); itr != x.end(); ++itr)
# define all(x) x.begin(), x.end()
# define allr(x) x.rbegin(), x.rend()

const static int mod = 1000000000 + 7;
const static int inf = INT_MAX / 2;
const static llong INF = LLONG_MAX / 2;
const static double eps = 1e-10;
const static int dx[] = {1, 0, -1, 0};
const static int dy[] = {0, 1, 0, -1};

template<class T> bool chmax(T &a, const T &b) { if (a < b) { a = b; return 1;} return 0;}
template<class T> bool chmin(T &a, const T &b) { if (b < a) { a = b; return 1;} return 0;}

char field[2001][2001];
int left_cnt[2001][2001], right_cnt[2001][2001], up_cnt[2001][2001], down_cnt[2001][2001];

signed main (int argc, char *argv[]) {
    cin.tie(0);
    ios::sync_with_stdio(false);

    int n, m;
    cin >> n >> m;
    rep(i, n) {
        string S;
        cin >> S;
        rep(j, m) {
            field[i][j] = S[j];
        }
    }

    for (int i = 0; i < n; ++i) {
        int cnt1 = 0;
        for (int j = 0; j < m; ++j) {
            if (field[i][j] == '.') {
                left_cnt[i][j] = cnt1;
                ++cnt1;
            } else {
                cnt1 = 0;
            }
        }

        int cnt2 = 0;
        for (int j = m - 1; j >= 0; --j) {
            if (field[i][j] == '.') {
                right_cnt[i][j] = cnt2;
                ++cnt2;
            } else {
                cnt2 = 0;
            }
        }
    }

    for (int j = 0; j < m; ++j) {
        int cnt1 = 0;
        for (int i = 0; i < n; ++i) {
            if (field[i][j] == '.') {
                up_cnt[i][j] = cnt1;
                ++cnt1;
            } else {
                cnt1 = 0;
            }
        }

        int cnt2 = 0;
        for (int i = n - 1; i >= 0; --i) {
            if (field[i][j] == '.') {
                down_cnt[i][j] = cnt2;
                ++cnt2;
            } else {
                cnt2 = 0;
            }
        }
    }

    llong res = 0;
    rep(i, n) {
        rep(j, m) {
            if (field[i][j] == '.') {
                res += (left_cnt[i][j] + right_cnt[i][j]) * (up_cnt[i][j] + down_cnt[i][j]);
            }
        }
    }

    cout << res << endl;

    return 0;
}