AISing Programming Contest 2019 C - Alternating Path(300)

C - Alternating Path

概要

のマスがあり、各マス目は黒または白に塗られている。
黒のマスと白のマスの組で、からまで下記の移動方法により到達可能な組の個数を求めよ。

• 上下左右の隣接マスへの移動を繰り返す
• 黒、白、黒、白…と色マスを交互に通るように移動する

制約

方針

色マスを交互に通ることで到達可能なマスを１つのグループとみなすと、そのグループ間では各マスに行き来することが可能である。逆に異なるグループ間のマスは行き来することができない。よって各グループごとに黒マスと白マスの組の個数を数えればよい。
組の個数は、グループ内の黒マスの個数×グループ内の白マスの個数で計算される。

グループ分けはDFSで実装し、グループ分け中に黒マスと白マスの個数をカウントし、DFSを抜けた際に
黒マスの個数×白マスの個数を足し合わせていった。

感想

実装に手間取った。最初はグループの色分けをやろうとしていたが、うまく通らず方針転換した。
WAが2回続き、バグの箇所を突き止めるためにリファクタリングしたら、それだけでACになった。
（リファクタリングになっていない）

解答

Submission #3988948 - AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
const int max_n = 1000;
int h, w;
string s[max_n];
 
bool u[max_n][max_n];
int vx[4] = {1, 0, -1, 0};
int vy[4] = {0, 1, 0, -1};
 
ll bc;
ll wc;
 
void dfs(int x, int y, bool b){
	u[x][y] = true;
	if(b){
		bc++;
	}else{
		wc++;
	}
 
	for(int i = 0; i < 4; i++){
		int nx = x + vx[i];
		int ny = y + vy[i];
 
		if(0 <= nx && nx < h && 0 <= ny && ny < w && !u[nx][ny]){
			if(b){
				if(s[nx][ny] == '.') dfs(nx, ny, !b);
			}else{
				if(s[nx][ny] == '#') dfs(nx, ny, !b);
			}
		}
	}
}
 
void sout(){
	rep(i, h){
		rep(j, w){
		   cout << s[i][j];
	   }
	   cout << endl;
	}
}
 
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	cin >> h >> w;
	rep(i, h) cin >> s[i];
	rep(i, h) rep(j, w) u[i][j] = false;
 
	ll ans = 0;
	rep(i, h){
		rep(j, w){
			bc = 0;
			wc = 0;
			if(!u[i][j]){
				dfs(i, j, s[i][j] == '#');
			}
			ans += bc * wc;
		}
	}
 
	cout << ans << endl;
}