# UVa 1103 - Ancient Messages

---
# 題目大意
給定H個16進位、長度為W的字串，用其二進位表示6種象形文字。如果是同一個象形文字，則黑色的部分會上下左右相連，而象形文字間不會相碰。要求辨識圖形中所有的象形文字，並按照字典序輸出。

---
# 題解
可以發現每種文字含有的空格數不同，因此可以藉由空格數辨識文字。
做三種BFS。首先將象形文字外部的空白去除，接著將文字的黑色部分跑一遍，此時碰到內部的白色格時再做一次BFS並記錄有幾塊白色。

---

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define pf push_front
#define ft first
#define sec second
#define pr pair<int,int>
#define ISCC ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std; 
int t ,n ,m ,vis[205][205] ,dir[][2] = {{1,0},{0,1},{-1,0},{0,-1}} ,sum ,cas;
string g[205] ,s ,ans;
string trans(int pos) //16進位轉2進位
{
	string res = "";
	int tp = ('0'<=s[pos] && s[pos]<='9')?(s[pos]-'0'):(10+s[pos]-'a');
	for(int i=0 ;i<4 ;i++) res = ((tp&(1<<i))?'1':'0') + res;
	return res;
}
void bfs(pr pos ,char type ,int sol) //sol代表要不要數區塊數
{
	queue<pr> que;
	que.push(pos);
	while(!que.empty())
	{
		pr now = que.front(); que.pop();
		if(vis[now.ft][now.sec]) continue;
		vis[now.ft][now.sec] = 1;
		for(int i=0 ;i<4 ;i++)
		{
			int x = now.ft+dir[i][0] ,y = now.sec+dir[i][1];
			if(x<0 || y<0 || x>n+1 || y>4*m+1 || vis[x][y]) continue;
			if(sol && g[x][y]=='0')
			{
				sum++;
				bfs({x,y} ,'0' ,0);
			}
			if(g[x][y] != type) continue;
			que.push({x,y});
		}
	}
}
int main()
{
	map<int ,char> mp;
	mp[1] = 'A';  mp[3] = 'J';  mp[5] = 'D'; 
	mp[4] = 'S';  mp[0] = 'W';  mp[2] = 'K'; 
	while(cin >> n >> m && n && m)
	{
		getchar(); string tp;
		tp = "";
		for(int i=1 ;i<=4*m+2 ;i++) tp += '0'; //用0圍一圈邊界 
		g[0] = g[n+1] = tp; 
		memset(vis,0,sizeof(vis));
		ans = "";
		for(int i=1 ;i<=n ;i++)	
		{
			getline(cin ,s); tp = "";
			for(int j=0 ;j<m ;j++) tp += trans(j);
			g[i] = '0'+tp+'0';
		}
		bfs({0,0} ,'0' ,0); //去除文字外的空白 
		for(int i=1 ;i<=n ;i++) 
			for(int j=1 ;j<=4*m ;j++) if(g[i][j] == '1' && !vis[i][j])
			{
				sum = 0; //紀錄白色區塊數
				bfs({i,j} ,'1' ,1);
				ans += mp[sum];
			}
		sort(ans.begin() ,ans.end()); //照字典序排好
		printf("Case %d: %s\n",++cas ,ans.c_str());
	} 
	return 0;
}