{"problem":{"name":"Alternating Path","description":{"content":"There is a grid with $H$ rows and $W$ columns, where each square is painted black or white. You are given $H$ strings $S_1, S_2, ..., S_H$, each of length $W$. If the square at the $i$\\-th row from th","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"aising2019_c"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $H$ rows and $W$ columns, where each square is painted black or white.\nYou are given $H$ strings $S_1, S_2, ..., S_H$, each of length $W$. If the square at the $i$\\-th row from the top and the $j$\\-th column from the left is painted black, the $j$\\-th character in the string $S_i$ is `#`; if that square is painted white, the $j$\\-th character in the string $S_i$ is `.`.\nFind the number of pairs of a black square $c_1$ and a white square $c_2$ that satisfy the following condition:\n\n*   There is a path from the square $c_1$ to the square $c_2$ where we repeatedly move to a vertically or horizontally adjacent square through an alternating sequence of black and white squares: black, white, black, white...\n\n## Constraints\n\n*   $1 \\leq H, W \\leq 400$\n*   $|S_i| = W$ ($1 \\leq i \\leq H$)\n*   For each $i$ ($1 \\leq i \\leq H$), the string $S_i$ consists of characters `#` and `.`.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$\n$S_1$\n$S_2$\n$:$\n$S_H$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"aising2019_c","tags":[],"sample_group":[["3 3\n.#.\n..#\n#..","10\n\nSome of the pairs satisfying the condition are $((1, 2), (3, 3))$ and $((3, 1), (3, 2))$, where $(i, j)$ denotes the square at the $i$\\-th row from the top and the $j$\\-th column from the left."],["2 4\n....\n....","0"],["4 3\n###\n###\n...\n###","6"]],"created_at":"2026-03-03 11:01:14"}}