2部グラフのマッチング

2008年のGoogle Code Jamをちょっとだけやった．
2部グラフのマッチングの応用があった．
模範回答（？）のコードが想像以上に短かった．

こんな感じ．

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

#define FILL(xs, x) memset(xs, x, sizeof((xs)))

const int M = 100, N = 100;
int m, n, ind, matchX[M][N], matchY[M][N], visited[M][N], count;
bool room[M][N];

bool dfs(int x, int y)
{
  if (x < 0) return true;
  if (visited[x][y] == count) return false;
  visited[x][y] = count;
  for (int i = x-1; i <= x+1; i++)
	for (int j = y-1; j <= y+1; j+=2)
	  if (0 <= i && i < m && 0 <= j && j < n && room[i][j])
		if ( dfs(matchX[i][j], matchY[i][j]) )
		  {
			matchX[i][j] = x; matchY[i][j] = y;
			matchX[x][y] = i; matchY[x][y] = j;
			return true;
		  }
  return false;
}

int solve()
{
  int ret = 0; count = 0;
  FILL(matchX,-1); FILL(matchY,-1); FILL(visited,0);

  for (int i = 0; i < m; i++)
	for (int j = 0; j < n; j++)
	  if (room[i][j])
        {
          ret++;
          if (j%2==1)
            {
              count++;
              if (dfs(i,j)) ret--;
            }
        }
  return ret;
}

int main()
{
  int testCase;
  cin >> testCase;
  for (int iCase = 1; iCase <= testCase; iCase++)
	{
	  cin >> m >> n;
	  for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
		  {
			char c;
			cin >> c;
			room[i][j] = c == '.';
		  }
	  cout << "Case #" << iCase << ": " << solve() << endl;
	}
  return 0;
}

無駄が無いコードになっている．再帰をつかって簡潔になっている．
2部グラフのマッチングはこういうふうに書ける，というのは常識なんでしょうか？