6 12_ancient_messages_uva1103 - nuaazdh/acm GitHub Wiki

##例题6-12 古代象形符号(Ancient Messages UVa1103) ###问题 给定5个象形文字的图案，然后要求根据输入的一个图案，输出图案中包含的象形字符（字母序输出）。输入的第一行为两个正整数H和W，表示图像的高度和宽度，后面的H行十六进制数表示图像内容，白色像素点为0，黑色像素点为1。输入以 0 0结束。 ###分析

乍一看不知道何从下手，然后根据给定的几个符号，发现了每个符号的特征：即任意两个符号的连通单元的个数不同，因此可以求一个图像的连通单元的个数来唯一确定该符号。如何求一个图像连通单元的个数呢？

联想上一题的种子填充，我们可以转向求连在白色格的数目。好了，已经找到如何确定一个符号的方法，那么一个图像中一共多少个符号？简单，求黑色格子的连通数目即可。

如何区分内部的白色和背景白色？开始想到的是用一个数组，记录黑色DFS过程中H和W的范围，在这个范围内统计白色，后来感觉太复杂。因为题目保证图案不触及边，所以直接来个把背景色置为非0和非1的即可。

###code in C++

#include <stdio.h>
#include <string.h>
#include <map>


#define  MAX_HEIGHT (210)
#define  MAX_WIDTH (60*4)


char map[MAX_HEIGHT][MAX_WIDTH];
char visit[MAX_HEIGHT][MAX_WIDTH];
char line[MAX_HEIGHT];

int dr[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
int height, width;
char dict[] = "WAKJSD";

int hex2dec(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    } else if (c >= 'a' && c <= 'f') {
        return 10 + c - 'a';
    } else {
        return 10 + c - 'A';
    }
}

int is_visit(int i, int j) {
    return (visit[i][j] == 1);
}

int is_valid_pos(int i, int j) {
    return (i >= 0 && i < height && j >= 0 && j < width);
}

void print_map(int h, int w) {
    int i, j;
    for (i = 0; i < h; ++i) {
        for (j = 0; j < w; ++j) {
            printf("%c", map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void dfs(int i, int j, char find, char set) {
    int di;
    if (!is_valid_pos(i, j) || map[i][j] != find)
        return;
    map[i][j] = set;
    visit[i][j] = 1;
    for (di = 0; di < 4; ++di) {
        if (map[i + dr[di]][j + dc[di]] == find && !is_visit(i + dr[di], j + dc[di])) {
            dfs(i + dr[di], j + dc[di], find, set);
        }
    }
}

void dfs_character(int i, int j, int &hole) {
    int di;
    if (!is_valid_pos(i, j) || is_visit(i, j))
        return;
    visit[i][j] = 1;
    for (di = 0; di < 4; ++di) {
        if (map[i + dr[di]][j + dc[di]] == '0' && !is_visit(i + dr[di], j + dc[di])) {
            ++hole;
            dfs(i + dr[di], j + dc[di], '0', ' ');
//            print_map(height, width);
        }
        if (map[i + dr[di]][j + dc[di]] == '1' && !is_visit(i + dr[di], j + dc[di])) {
            dfs_character(i + dr[di], j + dc[di], hole);
        }
    }
}


void find_character_count(int kcase) {
    int i, j;
    int hole;
    std::map<char, int> result;
    for (j = 0; j < width; ++j) {
        dfs(0, j, '0', ' '); // clear backgroud
        dfs(height - 1, j, '0', ' '); // clear backgroud
    }
    for(i=0;i<height;++i){
        dfs(i, 0 , '0', ' '); // clear backgroud
        dfs(i, width-1, '0', ' '); // clear backgroud
    }

//    print_map(height, width);
    for (i = 0; i < height; ++i) {
        for (j = 0; j < width; ++j) {
            hole = 0;
            if (map[i][j] == '1' && !is_visit(i, j)) {
                dfs_character(i, j, hole);
                if (result.count(dict[hole])) {
                    ++result[dict[hole]];
                } else {
                    result[dict[hole]] = 1;
                }
            }
        }
    }
    printf("Case %d: ", kcase);
    for (std::map<char, int>::iterator it = result.begin(); it != result.end(); ++it) {
        for (i = 0; i < it->second; ++i)
            printf("%c", it->first);
    }
    printf("\n");
}

int main() {
    int h, w, i, j, num, kcase = 0;
    while (scanf("%d%d", &h, &w) && h) {
        memset(map, 0, sizeof(map));
        memset(visit, 0, sizeof(visit));
        height = h;
        width = 4 * w;
        for (i = 0; i < h; ++i) {
            scanf("%s", line);
            for (j = 0; j < w; ++j) {
                num = hex2dec(line[j]);
                map[i][4 * j] = (num & (1 << 3)) ? '1' : '0';
                map[i][4 * j + 1] = (num & (1 << 2)) ? '1' : '0';
                map[i][4 * j + 2] = (num & (1 << 1)) ? '1' : '0';
                map[i][4 * j + 3] = (num & 0x01) ? '1' : '0';
            }
        }
//        print_map(height,width);
//        printf("Case %d:\n", ++kcase);
        find_character_count(++kcase);

    }
    return 0;
}

###点评

  1. 注意审题，题中有多个条件，其中一个说明，对角的黑色像素是不属于同一个图形的，所以方向只有4个，而不是8个；
  2. 清除背景的方法有点 ugly；
  3. 执行时间和第20名相同，0.013，考虑优化下

###改进

#include <stdio.h>
#include <string.h>
#include <map>

#define  MAX_HEIGHT (210)
#define  MAX_WIDTH (60*4)

char map[MAX_HEIGHT][MAX_WIDTH];
char line[MAX_HEIGHT];

int dr[] = {-1, 0, 1, 0}, dc[] = {0, -1, 0, 1};
int height, width;
char dict[] = "WAKJSD";

int hex2dec(char c) {
    if (c >= '0' && c <= '9') {
        return c - '0';
    } else if (c >= 'a' && c <= 'f') {
        return 10 + c - 'a';
    } else {
        return 10 + c - 'A';
    }
}

int is_valid_pos(int i, int j) {
    return (i >= 0 && i < height && j >= 0 && j < width);
}

void print_map(int h, int w) {
    int i, j;
    for (i = 0; i < h; ++i) {
        for (j = 0; j < w; ++j) {
            printf("%c", map[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

void dfs(int i, int j, char find, char set) {
    int di;
    map[i][j] = set;
    for (di = 0; di < 4; ++di) {
        if (is_valid_pos(i + dr[di], j + dc[di]) && map[i + dr[di]][j + dc[di]] == find) {
            dfs(i + dr[di], j + dc[di], find, set);
        }
    }
}

void dfs_character(int i, int j, int &hole) {
    int di;
    map[i][j] = ' ';
    for (di = 0; di < 4; ++di) {
        if (is_valid_pos(i + dr[di], j + dc[di]) && map[i + dr[di]][j + dc[di]] == '0') {
            ++hole;
            dfs(i + dr[di], j + dc[di], '0', ' ');
        }
        if (is_valid_pos(i + dr[di], j + dc[di]) && map[i + dr[di]][j + dc[di]] == '1') {
            dfs_character(i + dr[di], j + dc[di], hole);
        }
    }
}


void find_character_count(int kcase) {
    int i, j;
    int hole;
    std::map<char, int> result;
    // clear backgroud
    for (j = 0; j < width; ++j) {
        if (map[0][j] == '0') dfs(0, j, '0', ' ');
        if (map[height - 1][j] == '0') dfs(height - 1, j, '0', ' ');
    }
    for (i = 0; i < height; ++i) {
        if (map[i][0] == '0') dfs(i, 0, '0', ' ');
        if (map[i][width - 1] == '0') dfs(i, width - 1, '0', ' ');
    }
    // find the symbol
    for (i = 0; i < height; ++i) {
        for (j = 0; j < width; ++j) {
            hole = 0;
            if (map[i][j] == '1') {
                dfs_character(i, j, hole);
                if (result.count(dict[hole])) {
                    ++result[dict[hole]];
                } else {
                    result[dict[hole]] = 1;
                }
            }
        }
    }
    printf("Case %d: ", kcase);
    for (std::map<char, int>::iterator it = result.begin(); it != result.end(); ++it) {
        for (i = 0; i < it->second; ++i)
            printf("%c", it->first);
    }
    printf("\n");
}

int main() {
    int h, w, i, j, num, kcase = 0;
    while (scanf("%d%d", &h, &w) && h) {
        memset(map, 0, sizeof(map));
        height = h;
        width = 4 * w;
        for (i = 0; i < h; ++i) {
            scanf("%s", line);
            for (j = 0; j < w; ++j) {
                num = hex2dec(line[j]);
                map[i][4 * j] = (num & (1 << 3)) ? '1' : '0';
                map[i][4 * j + 1] = (num & (1 << 2)) ? '1' : '0';
                map[i][4 * j + 2] = (num & (1 << 1)) ? '1' : '0';
                map[i][4 * j + 3] = (num & 0x01) ? '1' : '0';
            }
        }
//        print_map(height,width);
        find_character_count(++kcase);
    }
    return 0;
}

###说明：

  1. 去掉了 visit， 因为背景色设置为空格，图案遍历以后也设置为空格，数完空洞后也设置为空格，这样不需要再记录那些点访问过；
  2. 去掉了 is_valid_pos 多处调用，放到if里面，这样不用进函数来判断，减少函数调用次数；
  3. 优化的结果执行时间还是0.013，╮(╯▽╰)╭
⚠️ **GitHub.com Fallback** ⚠️