uva1103_AncientMessages(找一幅图中有多少洞)

#include
using namespace std;
const int maxH = 200 + 5;
const int maxW = 50 + 5;
int H, W;
char buf[maxH][maxW<<2];
char color[maxH][maxW<<2];
bool vis[maxH][maxW<<2];
char *Hex2Bit[16] = {"0000", "0001", "0010", "0011",
"0100", "0101", "0110", "0111",
"1000", "1001", "1010", "1011",
"1100", "1101", "1110", "1111"};
char code[6] = {‘W‘, ‘A‘, ‘K‘, ‘J‘, ‘S‘, ‘D‘};
int dr[4] = {-1, 0, 1, 0};
int dc[4] = {0, 1, 0, -1};
//对非洞内0像素点填充2 ，以区分洞内0像素点
void dfs(int r, int c)
{
buf[r][c] = ‘2‘;
vis[r][c] = true;
for(int i = 0; i <4; i++){
int rr = r + dr[i];
int cc = c + dc[i];
if(rr > 0 && rr 1 && cc > 0 && cc 4 + 1 &&
buf[rr][cc] == ‘0‘ && !vis[rr][cc]){
dfs(rr, cc);
}
}
}
int cnt;
//对洞0像素点填充2，
void dfs2(int r, int c)
{
buf[r][c] = ‘2‘;
vis[r][c] = true;
for(int i = 0; i <4; i++){
int rr = r + dr[i];
int cc = c + dc[i];
if(rr > 0 && rr 1 && cc > 0 && cc 4 + 1){
if(buf[rr][cc] == ‘0‘){
cnt++;
dfs(rr, cc);
}
if(buf[rr][cc] == ‘1‘ && !vis[rr][cc]){
dfs2(rr, cc);
}
}
}
}
int main()
{
// freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
int kase = 0;
while(cin >> H >> W && H && W){
memset(vis, 0, sizeof(vis));
char s[maxW];
for(int i = 1; i <= H; i++){
scanf("%s", s);
int len = strlen(s);
for(int j = 0; j ){
int idx = s[j] >= ‘a‘ ? s[j] - ‘a‘ + 10 : s[j] - ‘0‘;
strncpy(buf[i] + 4*j + 1, Hex2Bit[idx], 4);
}
//printf("%s\n", buf[i]);
}
// for(int i = 0; i <= H + 1; i++){
// for(int j = 0; j <= (W<<2) + 1; j++){
// printf("%c", buf[i][j]);
// }
// printf("\n");
// }
//dfs将外面的空白全标记为‘2‘，以区分内白格。
for(int j = 1; j <= (W<<2); j++){
if(buf[1][j] == ‘0‘){
dfs(1, j);
}
if(buf[H][j] == ‘0‘){
dfs(H, j);
}
}
for(int i = 1; i <= H; i++){
if(buf[i][1] == ‘0‘){
dfs(i, 1);
}
if(buf[i][W<<2] == ‘0‘){
dfs(i, W<<2);
}
}
// for(int i = 0; i <= H + 1; i++){
// for(int j = 0; j <= (W<<2) + 1; j++){
// printf("%c", buf[i][j]);
// }
// printf("\n");
// }
vector<char>ans;
for(int i = 1; i <= H; i++){
for(int j = 1; j <= (W<<2); j++){
if(buf[i][j] == ‘1‘){
cnt = 0;
dfs2(i, j);
ans.push_back(code[cnt]);
}
}
}
sort(ans.begin(), ans.end());
printf("Case %d: ", ++kase);
for(auto i : ans){
cout << i;
}
cout << endl;
}
return 0;
}