AISing Programming Contest 2019 C - Alternating Path

考えたこと：

・メモ化再帰

ー＞重複が取り除けない・・・

ー＞偶奇で場合分けしたりするのだるすぎる・・・

・数え上げていく

ー＞これも微妙・・・

・組み合わせの計算に持ち込む。

ー＞どうやって？

左端上の点を固定して考えようとしていましたが、これが間違いでした・・・

実験をしていくと・・・

・考えればいいのは、白黒が交互に並ぶ部分だけ。（この部分を連結な部分と呼ぶことにする。）

・連結部の白の個数と黒の個数がわかれば、スタート点とゴール点の個数が決まる。

・任意のスタート点からゴール点へ移動することができる。（理由：連結）

これらを踏まえて、連結部分のもとめる点の組の個数は、

黒点の数　＊　白点の数　に等しい。

また、各点において訪れたかどうかの判定をbool vis[]などで記録しておけば、各点を訪れる回数は高々一回。

ゆえに　計算量はＯ（Ｈ＊Ｗ）

実装：

#include <bits/stdc++.h>
using namespace std;
#define int long long

int H, W;
string s[410];
bool vis[410][410];

int dx[] = {-1, 0 ,0 ,1};
int dy[] = {0, -1, 1, 0};

int x = 0, y = 0;

void rec(int h, int w) {
  if (vis[h][w] == true) return;
  vis[h][w] = true;
  for (int i = 0; i < 4; i++) {
    int ny = h + dy[i], nx = w + dx[i];
    if (ny >= H || ny < 0 || nx >= W || nx < 0 || vis[ny][nx] || s[ny][nx] == s[h][w]) continue;
    rec(ny, nx);
  }

  if (s[h][w] == '.') {
    x++;
  } else {
    y++;
  }
  return;
}

signed main() {
  cin >> H >> W;
  for (int i = 0; i < H; i++) {
    cin >> s[i];
  }

  int ans = 0;
  for (int h = 0; h < H; h++) {
    for (int j = 0; j < W; j++) {
      rec(h, j);
      ans += x * y;
      x = 0;
      y = 0;
    }
  }

  cout << ans << endl;
  return 0;
}

xが黒点の個数、yが白点の個数で、グローバル変数で持たせた。

（お行儀が悪い。）

連結部分ごとに考えるので、x=y=0を忘れないよう注意。