DP とかメモ化再帰とか考え出すとドツボにはまる...素直な考察が大事だね。

問題概要

$H \times W$ のグリッドが与えられる。各マスは白か黒で塗られている。「黒」マスと「白」マスのペアであって、

黒マスから出発して、隣接するマスを辿っていくことで白マスに到達する経路が存在して
その経路上のマスが黒白黒白...と黒と白が交互に表れている

ようなものを数え上げよ。

制約

$1 \le H, W \le 400$

考えたこと

一瞬、

各黒マスについて、そこから行くことのできる白マスをすべて求める (BFS とかでできる)

とやりたくなる。が、これだと $O(H^{2}W^{2})$ かかってしまって間に合わない。そこでちょっと考察してみる。

ある黒マス u と、ある黒マス v とが、白黒交互パスによって互いに行き来できるとき、

u から行くことのできる白マスの個数
v から行くことのできる白マスの個数

は等しい

ということがわかる。よって、各マスに対し、「互いに行き来できる関係」ごとに分解したくなる。そう考えると、想定解法のような連結成分分解は自然に着想できる気がする。

すなわち、グリッドの各マス間に対し

隣接している
色が異なっている (白同士、黒同士はダメ)

ところに辺を張ったグラフを想起して、そのグラフを連結成分ごとに分解すればいい。この各連結成分については、

任意の黒マスから、任意の白マスへと、白黒交互パスでいくことができる

という性質をもつので、「黒マスの個数 × 白マスの個数」を求めて、それを連結成分ごとに合計する。

連結成分分解は

Union-Find
DFS
BFS

のどれでやっても OK

#include <iostream>
#include <vector>
#include <string>
using namespace std;

int dx[4] = {1, 0, -1, 0};
int dy[4] = {0, 1, 0, -1};
const int MAX = 410;
using pint = pair<int,int>;

int H, W;
vector<string> fi;

long long numb = 0, numw = 0;
bool seen[MAX][MAX];
void dfs(int x, int y) {
    seen[x][y] = true;
    if (fi[x][y] == '#') ++numb;
    else ++numw;
    
    for (int dir = 0; dir < 4; ++dir) {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
        if (fi[x][y] == fi[nx][ny]) continue; // 隣接マスの色が同じだったら分断されている
        if (seen[nx][ny]) continue;
        dfs(nx, ny);
    }
}

int main() {
    cin >> H >> W;
    fi.resize(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];
    
    long long res = 0;
    for (int x = 0; x < H; ++x) {
        for (int y = 0; y < W; ++y) {
            if (fi[x][y] == '.') continue;
            if (seen[x][y]) continue;
            numb = numw = 0; // 黒マスと白マスの個数を 0 で初期化
            dfs(x, y);
            res += numb * numw;
        }
    }
    cout << res << endl;
}