Uva1103 ancient pictograph recognition

  Title Stem

         In order to understand the early civilization , Archaeologists often learn texts written in ancient languages . There is such a language , It was first used in Egypt 3000 years ago . This language is based on pictographic symbols . Below are six hieroglyphs and their names . In this case , You will write a program to recognize these six symbols .

  Input

        These inputs contain multiple test samples , Each sample represents an image that contains one or more of the above symbols . These images are given in the form of black coordinates and white coordinates contained in the horizontal scan line . In these input data , Each scan line is encoded in hexadecimal . for example , Sequence of eight coordinates "10011100"( A black pixel , Then two white pixels ……) Expressed as 16 Hexadecimal "9c".16 Only numbers and lowercase letters are used in hexadecimal . The first line of input for each sample contains two integers （H and W）H(0< H <= 200) Said line ,W（0 < W <= 50） The column . Input image data from top to bottom .

The input image form meets the following rules ：

1. The image contains only the above six symbols ;
2. Each image has at least one valid symbol ;
3. Each black coordinate is part of the symbol ;
4. Each ideograph consists of a connected set of black pixels , Each black pixel is on top of it 、 Bottom 、 Left side 、 Right side 、 At least one other black pixel ;
5. Symbols do not coincide with each other and do not contain ;
6. Two diagonal contact black pixels always have a common contact black pixel
7. Symbols can be distorted , But each symbol has a symbol that is topologically equivalent to the symbol in the figure above （ If two graphs are topologically equivalent , It means that it can be pulled down and stretched into another figure without tearing ）

        The final sample input contains two 0

Output

        For each example , Use the following code to display its sample number , Followed by a string , The string contains one character of each ideograph recognized in the image . Each output string , Print in alphabetical order

Ankh: A        Wedjat: J        Djed: D        Scarab: S        Was: W        Akhet: K

Sample input

100 25

0000000000000000000000000

0000000000000000000000000

...(50 lines omitted)...

00001fe0000000000007c0000

00003fe0000000000007c0000

...(44 lines omitted)...

0000000000000000000000000

0000000000000000000000000

150 38

00000000000000000000000000000000000000

00000000000000000000000000000000000000

...(75 lines omitted)...

0000000003fffffffffffffffff00000000000

0000000003fffffffffffffffff00000000000

...(69 lines omitted)...

00000000000000000000000000000000000000

00000000000000000000000000000000000000

  Sample output

Case 1: AKW

Case 2: AAAAA

Ideas

         You can find by counting holes , The number of white holes in the six symbols is 1 3 5 0 2. So just go through DFS Judging the number of white connecting blocks inside them can identify characters . The general programming idea is as follows ：

1. First convert the data from hexadecimal to binary
2. DFS Whole block matrix . Label the connecting blocks respectively . The white mark at the bottom is marked first as 1. The connection block here includes ： Bottom , Black border , White blocks within the black border .
3. Then, according to the number of white blocks related to the black boundary , Decision symbol .

   #include <iostream>
   #include <algorithm>
   #include <unordered_map>
   #include <unordered_set>
   #include <vector>
   #include <string>
   using namespace std;
   string hextobin(const string &hex); // Binary conversion , One 16 Convert a binary number to four binary numbers 
   void dfs(int row, int col, int count);
   void calhole(int row, int col);                           // Count the number of white holes corresponding to the black frame 
   unordered_map<char, string> hexmp;                        // Match binary to sixteen mechanism 
   unordered_map<int, unordered_set<int>> nhole;             // Marking value of the hole corresponding to the corresponding black edge 
   vector<string> pic;                                       // floor 
   vector<vector<int>> tag;                                  // Marker plate 
   int h, m;                                                 // The ranks of 
   int direction[4][2] = {
        {1, 0}, {-1, 0}, {0, -1}, {0, 1}}; // Express dfs Four directions of 
   int main()
   {
       hexmp['0'] = "0000";
       hexmp['1'] = "0001";
       hexmp['2'] = "0010";
       hexmp['3'] = "0011";
       hexmp['4'] = "0100";
       hexmp['5'] = "0101";
       hexmp['6'] = "0110";
       hexmp['7'] = "0111";
       hexmp['8'] = "1000";
       hexmp['9'] = "1001";
       hexmp['a'] = "1010";
       hexmp['b'] = "1011";
       hexmp['c'] = "1100";
       hexmp['d'] = "1101";
       hexmp['e'] = "1110";
       hexmp['f'] = "1111";
       const char *wordmp = "WAKJSD"; // Match the number of holes to the text 
       int n = 0;
       while (cin >> h >> m && h)
       {
           getchar();     // Remove line breaks 
           m = m * 4 + 2; // After converting to binary , The number of columns has quadrupled . And added two columns 
           pic.clear();
           pic.push_back(string(m, '0')); // Add all in the first line 0 A line 
           string hex;
           for (int i = 0; i < h; i++)
           {
               getline(cin, hex);                        // Read a line 
               pic.push_back("0" + hextobin(hex) + "0"); // Convert this line to binary , Then store it on the backplane pic in , Add all in the first column 0 A list of 
           }
           pic.push_back(string(m, '0')); // Add all at the end of the line 0 A line 
           h += 2;                        // Added two lines 
   
           tag.clear();
           for (int i = 0; i < h; i++)
               tag.push_back(vector<int>(m, 0)); // Generate h That's ok m Column 0 Matrix . To record “ Connect blocks with numbers ” Data for 
   
           int count = 0; // Unicom block tag value , It also represents the number of connected blocks 
           nhole.clear();
           for (int i = 0; i < h; i++) //dfs All coordinates 
               for (int j = 0; j < m; j++)
                   if (tag[i][j] == 0)
                   {
                       dfs(i, j, ++count);
                       if (pic[i][j] == '1') // Records are black edged labels 
                           nhole[count];     // If nhole There is no subscript in count, Add , If there is , No operation , If there is no statistics here , It will be missed W, Because W There is no white connecting block inside ,calhole Can't count 
                   }
   
           for (int i = 0; i < h; i++)
               for (int j = 0; j < m; j++)
                   if (pic[i][j] == '1') // If it's a black border 
                       calhole(i, j);
   
           string ans;
           ans.clear();
           for (auto hole : nhole) // Convert the number of holes in each to text 
               ans.push_back(wordmp[hole.second.size()]);
           sort(ans.begin(), ans.end());
           cout << "Case " << ++n << ": " << ans << endl;
       }
       return 0;
   }
   
   string hextobin(const string &hex)
   {
       string bin{""};
       for (auto i : hex)
           bin += hexmp[i];
       return bin;
   }
   
   void dfs(int row, int col, int count)
   {
       tag[row][col] = count; // Mark the current coordinate value 
       for (auto i : direction)
       {
           int row2 = row + i[0];
           int col2 = col + i[1];
           // The new coordinates should be within the range 、 Not marked and the same color as the old coordinates 
           if (row2 >= 0 && row2 < h && col2 >= 0 && col2 < m && tag[row2][col2] == 0 && pic[row2][col2] == pic[row][col])
               dfs(row2, col2, count);
       }
   }
   
   void calhole(int row, int col)
   {
       for (auto i : direction)
       {
           int row2 = row + i[0];
           int col2 = col + i[1];
           /* If the tag value is within a reasonable range 、 Not equal and the new coordinate's marker value is not 1（ That is, it is not a white back plate ）
            Add the tag value to the corresponding black tag value .
            Be careful ： Add a duplicate tag value to a black tag value , Use here set The element does not repeat */
           if (row2 >= 0 && row2 < h && col2 >= 0 && col2 < m && tag[row][col] != tag[row2][col2] && tag[row2][col2] != 1)
               nhole[tag[row][col]].insert(tag[row2][col2]);
       }
   }