LoginSignup
1
0

More than 3 years have passed since last update.

【AtCoder】Mujin Programming Challenge 2018 C - 右折

Last updated at Posted at 2019-03-14

Mujin Programming Challenge 2018 C - 右折

問題概要

C - 右折

解法

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

IMG_1067.jpg

上図のようなフィールドで、マス(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;
}
1
0
1

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0