AISing Programming Contest 2019 C - Alternating Path
こんな問題
#(黒)と.(白)で構成されたグリッドが与えられるので、黒から始まり、上下左右に移動を繰り返して黒・白・黒…白となるような始点と終点の組の合計数を出力してください。
ポイント
- 気をつけないとTLEしてしまう
問題文の理解と考察
まず入出力例1を見てみる。(1,2)と(3,3), (3,1)と(3,2) などがあるそう。図に表すと(黒はX、白は◯にしています)
どちらも黒から始まり、黒、白…となっています。このような始点と終点の組の数を探せばいいらしい。
自分の考え(TLE)
始点は必ず黒になるので、一つ一つのマスを順に確認していき、もしそれが黒ならそこから深さ優先探索で白と黒を交互に探せるだけ探していき、新しく白を見つけた時にカウントしていけば数は求まるのでは？
void dfs(int y, int x) { 訪問したことにする if (白なら) { 答え++; for (4回繰り返す) { if (配列から出ていない) { if (未訪問 && 行き先が黒) { dfs(行き先); } } } } else { for (4回繰り返す) { if (配列から出ていない) { if (未訪問 && 行き先が白) { dfs(行き先); } } } } } int main() { for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (m[i][j] == '#') { dfs(i, j); } } } cout << 答え << endl; }
こういう感じのコードを書いた。TLEした。
この問題の罠
#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#
#.#.#.#.#.#.#.#.#.#.#.#.#.#.
.#.#.#.#.#.#.#.#.#.#.#.#.#.#
これの400×400版。さっきの方法だとTLEする。考え方を変えないといけない。
時短テク
- 白を通して繋がっている黒たちは全て組の数が同じだったので、白の数×黒の数で一度に求められるらしい。
例えば入力が
4 4
.#..
..#.
...#
#...
の時、全ての組み合わせを列挙すると、
こうなります。赤が始点で、青が終点です。上の3行を比較すると、「終点が全く同じ」ということがわかります。白を経由して移動できる黒(繋がっている黒)は、互いに移動が可能なので、終点の数は同じになります。この場合、6×3で18になります。この性質を利用すると、TLEを回避することができます。自分の場合は、whiteとblackの数をカウントしていきました。そしてwhite×blackする感じです(すごい説明が雑ですいません)。
メモ
400×400の難しいやつ、全てが繋がっているのでblack = 400*400/2, white = 400*400/2 になり、一見最大でもintの範囲内なのでどちらもintにしたくなりますが、
ll ans = black * white;
とした時に、black*whiteがintの範囲を超えてオーバーフローした状態でllに代入されます。知らなかったのでWAりました。気をつけましょう。
自分の解答(AC)
#include <bits/stdc++.h> using namespace std; typedef long long int ll; int dx[4] = {0, 1, 0, -1}; int dy[4] = {1, 0, -1, 0}; bool went[410][410]; char m[410][410]; int h, w; ll white = 0; ll black = 0; void dfs(int y, int x) { went[y][x] = true; if (m[y][x] == '.') { white++; for (int i = 0; i < 4; i++) { if (0 <= y + dy[i] && y + dy[i] < h && 0 <= x + dx[i] && x + dx[i] < w) { if (!went[y + dy[i]][x + dx[i]] && m[y + dy[i]][x + dx[i]] == '#') { dfs(y + dy[i], x + dx[i]); } } } } else { black++; for (int i = 0; i < 4; i++) { if (0 <= y + dy[i] && y + dy[i] < h && 0 <= x + dx[i] && x + dx[i] < w) { if (!went[y + dy[i]][x + dx[i]] && m[y + dy[i]][x + dx[i]] == '.') { dfs(y + dy[i], x + dx[i]); } } } } } int main() { cin >> h >> w; for (int i = 0; i < h; i++) cin >> m[i]; ll ans = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (m[i][j] == '#' && went[i][j] == 0) { white = 0; black = 0; dfs(i, j); ans += white * black; } } } cout << ans << endl; }
