Uva1103

题目地址：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=838&page=show_problem&problem=3544

分析：

这道题本质就是DFS求连通块，但是这道题并不单纯，涉及到：

• 输入格式的进制转化，16进制转化为二进制存储
• 求连通块，包括白色连通块，以及黑色连通块
• 求黑色连通块内部的白色连通的数量
• 排序输出

现在再概括性地描述下代码的逻辑步骤：

• 首先是读入数据，并将16进制数转化为二进制存储进新的矩阵中
• 扫描整个新的二进制矩阵，运用常规的dfs递归找出所有的连通块，包括白色和黑色连通块，并且标上编号存储进color数组中。注意保存黑色连通块的编号进vector容器中
• 扫描整个新的二进制矩阵，找出黑色像素对应的连通块内部的白色连通块，并将内部的白色连通块编号存储进以黑色连通块编号为下标的vector<set<> >中，求每个黑色连通编号作为下标的set<>的size（）即可求得对应的输出编码。最后进行sort排序输出即可

代码如下:

// UVa1103 Ancient Messages
// Rujia Liu
// we pad one empty line/column to the top/bottom/left/right border, so color 1 is always "background" white
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<set>
using namespace std;

char bin[256][5];

const int maxh = 200 + 5;
const int maxw = 50 * 4 + 5;

int H, W, pic[maxh][maxw], color[maxh][maxw];
char line[maxw];

 
void decode(char ch, int row, int col) {
  for(int i = 0; i < 4; i++)
    pic[row][col+i] = bin[ch][i] - '0';     
}

const int dr[] = {-1, 1, 0, 0};
const int dc[] = {0, 0, -1, 1};

// dfs from (row, col) and paint color c
void dfs(int row, int col, int c) {     //进行递归遍历找出所有连通块并且将编号存储进color数组中,外层连通块即"背景"首先被编号为1。 
  color[row][col] = c;
  for(int i = 0; i < 4; i++) {  //递归矩阵相邻的8个元素 
    int row2 = row + dr[i];
    int col2 = col + dc[i];
    if(row2 >= 0 && row2 < H && col2 >= 0 && col2 < W && pic[row2][col2] == pic[row][col] && color[row2][col2] == 0)    //颜色相同，不越界，没有被涂色则进行递归调用 
      dfs(row2, col2, c);
  }
}

vector<set<int> > neighbors;        //neighbors下标是黑色连通块的编号，值set<>是存储的是内部的所有白色连通块编号 

void check_neighbors(int row, int col) {        //扫描黑色连通块内部的白色连通块 
  for(int i = 0; i < 4; i++) {
    int row2 = row + dr[i];
    int col2 = col + dc[i];
    if(row2 >= 0 && row2 < H && col2 >= 0&& col2 < W && pic[row2][col2] == 0 && color[row2][col2] != 1)     //是白色连通块，并且不是外部的白色背景 
      neighbors[color[row][col]].insert(color[row2][col2]);
  }
}

const char* code = "WAKJSD";    //可以通过code[内部白色连通块的数量]获得对应的象形文字编码 

char recognize(int c) {
  int cnt = neighbors[c].size();
  return code[cnt];
}

// use this function to print the decoded picture
void print() {
  for(int i = 0; i < H; i++) {
    for(int j = 0; j < W; j++) printf("%d", pic[i][j]);
    printf("n");
  }
}

int main() {
  strcpy(bin['0'], "0000");     //'0'作为数组下标为转为30,bin[30][]存储"0000" 
  strcpy(bin['1'], "0001");     
  strcpy(bin['2'], "0010");
  strcpy(bin['3'], "0011");
  strcpy(bin['4'], "0100");
  strcpy(bin['5'], "0101");
  strcpy(bin['6'], "0110");
  strcpy(bin['7'], "0111");
  strcpy(bin['8'], "1000");
  strcpy(bin['9'], "1001");
  strcpy(bin['a'], "1010");
  strcpy(bin['b'], "1011");
  strcpy(bin['c'], "1100");
  strcpy(bin['d'], "1101");
  strcpy(bin['e'], "1110");
  strcpy(bin['f'], "1111");

  int kase = 0;
  while(scanf("%d%d", &H, &W) == 2 && H) {
    memset(pic, 0, sizeof(pic));
    for(int i = 0; i < H; i++) {
      scanf("%s", line);
      for(int j = 0; j < W; j++)
        decode(line[j], i+1, j*4+1);        //输入的16进制数转化为二进制数，存入相应长宽的二维矩阵中，并且需要注意的是row+1,col+1是为了在第一行和第一列的矩阵加一层0，方便求背景白色的连通块 
    }

    H += 2;             //为了遍历新的二进制矩阵而变换下标范围 
    W = W * 4 + 2;

    int cnt = 0;    //连通变量 
    vector<int> cc;  //存储黑色连通块的编号 
    memset(color, 0, sizeof(color));
    for(int i = 0; i < H; i++)      //遍历整个二进制数矩阵 
      for(int j = 0; j < W; j++)
        if(!color[i][j]) {      //如果对应块没有被涂色，则进行dfs求连通块 
          dfs(i, j, ++cnt);
          if(pic[i][j] == 1) cc.push_back(cnt);     //保存了黑色像素连通的编号 
        }

    neighbors.clear();
    neighbors.resize(cnt+1);
    for(int i = 0; i < H; i++)      //扫描整个二进制矩阵，扫描黑色像素对应连通块内部的白色连通块，并将其存放在vector<set<>> 容器中 
      for(int j = 0; j < W; j++)
        if(pic[i][j] == 1)
          check_neighbors(i, j);

    vector<char> ans;               
    for(int i = 0; i < cc.size(); i++) //获得整个二进制矩阵，黑色连通块的编号，并在容器neighbors中取得其内部白色连通块的数量，通过数量可得对应的象形文字编码 
      ans.push_back(recognize(cc[i]));      //编码入vector<>容器后进行排序。 
    sort(ans.begin(), ans.end());

    printf("Case %d: ", ++kase);
    for(int i = 0; i < ans.size(); i++) printf("%c", ans[i]);
    printf("n");
  }
  return 0;
}

总结

本题题目甚长，代码甚长，技巧甚妙，细节甚繁，可谓脑子不够用。。非吾等菜鸡可手敲AC之，本人又甚愚钝，单看就看了2个小时有余。。。。故仅仅在原始代码上加上了个人的注释理解，希望可以给看不懂代码的人一些帮助