Mujin Programming Challenge 2018 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;
}