例题6-13 古代象形符号（Ancient Messages, World Finals 2011, UVa 1103）

思路:
1. 按照每个图形中的空白区域个数来区分图形。
2. 先进行一次dfs将外围全部填充，把区域划分为多个。
3. 对单块区域处理，从黑色开始dfs，在其中有白色则填充并计数，同时把黑色填充。

#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <algorithm>
#include <functional>
#include <utility>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <cctype>
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define IN() freopen("in.txt", "r", stdin)
#define OUT() freopen("out.txt", "w", stdout)
#define LL long long
#define maxn 205
#define maxm 6000005
#define mod  10007
#define INF 1000000007
#define EPS 1e-7
#define PI 3.1415926535898
#define N 4294967296
using namespace std;
//-------------------------CHC------------------------------//
int a[maxn][maxn];
int n, m, cnt;
const int dx[] = { 1, -1, 0, 0 }, dy[] = { 0, 0, 1, -1 };
const char code[] = "WAKJSD";
map<char, int> _hex;
vector<char> ans;

void dfs(int x, int y) {
	if (x < 0 || x > n+1 || y < 0 || y > m+1) return;
	a[x][y] = 2;
	for (int i = 0; i < 4; ++i) {
		int xx = x + dx[i], yy = y + dy[i];
		if (a[xx][yy] == 0) dfs(xx, yy);
	}
}

void dfs2(int x, int y) {
	if (x < 0 || x > n+1 || y < 0 || y > m+1) return;
	a[x][y] = 2;
	for (int i = 0; i < 4; ++i) {
		int xx = x + dx[i], yy = y + dy[i];
		if (a[xx][yy] == 0) dfs(xx, yy), ++cnt;
		else if (a[xx][yy] == 1) dfs2(xx, yy);
	}
}

void debug() {
	for (int i = 0; i <= n+1; ++i) {
		for (int j = 0; j <= m+1; ++j) printf("%d", a[i][j]);
		puts("");
	}
	puts("");
}

int main() {
	//IN(); OUT();
	int kase = 1;
	for (int i = 0; i < 10; ++i) _hex['0' + i] = i;
	for (int i = 0; i < 6; ++i) _hex['a' + i] = 10 + i;
	while (scanf("%d%d", &n, &m) && (n && m)) {
		ans.clear();
		CLEAR(a, 0);
		char s[55];
		for (int i = 1; i <= n; ++i) {
			scanf("%s", s);
			for (int j = 0, k = 1; j < m; ++j, k += 4) {
				for (int t = 0; t < 4; ++t) 
					a[i][k + t] = _hex[s[j]] >> (3 - t) & 1;
			}
		}
		m <<= 2;
		dfs(0, 0);
		//debug();
		for(int i = 1; i <= n; ++i) 
			for(int j = 1; j <= m; ++j) 
				if (a[i][j] == 1) {
					cnt = 0;
					dfs2(i, j);
					ans.push_back(code[cnt]);
				}
		printf("Case %d: ", kase++);
		sort(ans.begin(), ans.end());
		for (int i = 0; i < ans.size(); ++i) printf("%c", ans[i]);
		puts("");
	}
	return 0;
}