TopCoder SRM 533 Div1 Medium: MagicBoard

解法

各列・各行をそれぞれ1つの頂点とみなし，列->行->列->行->...というように全ての頂点を通ることができれば良い．
一筆書きできるかどうかはオイラー閉路の考え方で頂点の次数を調べれば良い．

コード

public class MagicBoard {
	boolean[][] graph;
	boolean[] visited;

	public String ableToUnlock(String[] board) {
		int R = board.length;
		int C = board[0].length();
		int[] degree = new int[R + C];// 頂点の次数
		graph = new boolean[R + C][R + C];
		for (int r = 0; r < R; r++) {
			for (int c = 0; c < C; c++) {
				if (board[r].charAt(c) == '#') {
					degree[r]++;
					degree[c + R]++;
					graph[r][c + R] = true;
					graph[c + R][r] = true;
				}
			}
		}

		// 奇数の行・列の数をカウントする
		int oddCols = 0;
		int oddRows = 0;
		for (int c = 0; c < C; ++c) {
			if (degree[c + R] % 2 != 0) {
				oddCols++;
			}
		}
		for (int r = 0; r < R; r++) {
			if (degree[r] % 2 != 0) {
				oddRows++;
			}
		}

		// どうやっても無理な時
		if (oddCols + oddRows > 2) {
			return "NO";
		}

		/*
		 * スタートはcol->rowの移動だから, 始点はcolの頂点になる． 奇数の次数をもつcolの頂点が2個あることは問題ないが,
		 * 奇数の次数をもつrowの頂点が2個あると出来ない．
		 */
		if (oddRows == 2 && oddCols == 0) {
			return "NO";
		}

		// 全ての辺が連結かどうか調べる
		visited = new boolean[R + C];
		for (int v = 0; v < R + C; v++) {
			if (degree[v] > 0) {
				dfs(v);
				break;
			}
		}
		for (int v = 0; v < R + C; v++) {
			if (degree[v] > 0 && !visited[v]) {
				return "NO";
			}
		}
		return "YES";
	}

	private void dfs(int start) {
		if (visited[start]) {
			return;
		}

		visited[start] = true;
		for (int i = 0; i < graph[start].length; i++) {
			if (graph[start][i]) {
				dfs(i);
			}
		}
		return;
	}

}