UVa-1103 Ancient Messages

  1 #include <bits/stdc++.h>
  2 
  3 using namespace std;
  4 
  5 const int maxn = 200;
  6 char g[maxn+3][maxn+3];
  7 int idx[maxn][maxn];
  8 int m,n;
  9 string result;
 10 
 11 string hex2bin(char c)
 12 {
 13     int index;
 14     if(c<='9')
 15         index = c-'0';
 16     else if(c=='a')
 17         index = 10;
 18     else if(c=='b')
 19         index = 11;
 20     else if(c=='c')
 21         index = 12;
 22     else if(c=='d')
 23         index = 13;
 24     else if(c=='e')
 25         index = 14;
 26     else
 27         index = 15;
 28 
 29     vector<string> List
 30     {
 31         "0000","0001","0010","0011",
 32         "0100","0101","0110","0111",
 33         "1000","1001","1010","1011",
 34         "1100","1101","1110","1111"
 35     };
 36     return List[index];
 37 }
 38 
 39 void makeGraph(char c,int x,int y)
 40 {
 41     string contain = hex2bin(c);
 42     y *= 4;
 43     for(int i = 0; i< 4; i ++)
 44     {
 45         g[x][y+i] = contain[i];
 46     }
 47 }
 48 
 49 void dfs3(int r,int c)
 50 {
 51     if(r<0 || r>=m || c<0 || c>= 4*n) return ;//出界
 52     if(idx[r][c]>0 || g[r][c]!='0')    return ;
 53     g[r][c] = -1;
 54     idx[r][c] = 1;
 55 
 56     for(int dr = -1; dr <= 1; dr ++)
 57         for(int dc = -1; dc <= 1; dc ++)
 58             if(dr != 0 || dc != 0)
 59                 dfs3(r+dr,c+dc);
 60 }
 61 
 62 void dfs1()
 63 {
 64     for(int i = 1; i <= m-2; i ++)
 65     {
 66         dfs3(i,0);
 67         dfs3(i,4*n-1);
 68     }
 69     for(int i = 0; i <= 4*n-1; i ++)
 70     {
 71         dfs3(0,i);
 72         dfs3(m-1,i);
 73     }
 74 }
 75 
 76 void dfs2(int r,int c,int &cnt)
 77 {
 78     if(r<0 || r>=m || c<0 || c>= 4*n) return ;//出界
 79     if(idx[r][c]>0 || g[r][c]!='1')    return ;
 80     g[r][c] = -1;
 81     idx[r][c] = 1;
 82 
 83     for(int dr = -1; dr <= 1; dr ++)
 84         for(int dc = -1; dc <= 1; dc ++)
 85             if(dr != 0 || dc != 0)
 86             {
 87                 if(g[r+dr][c+dc]=='0')
 88                 {
 89                     cnt ++;
 90                     dfs3(r+dr,c+dc);
 91                 }
 92                 dfs2(r+dr,c+dc,cnt);
 93             }
 94 }
 95 
 96 int kase = 0;
 97 
 98 int main()
 99 {
100     while(cin >> m >> n)
101     {
102         if(m==0&&n==0)
103             break;
104         char tmpInput;
105         memset(idx,0,sizeof(idx));
106         result.clear();
107 
108         for(int i = 0; i < m; i ++)
109         {
110             for(int j = 0; j < n; j ++)
111             {
112                 cin >> tmpInput;
113                 makeGraph(tmpInput,i,j);
114             }
115         }
116 
117         dfs1();
118 
119         for(int i = 0; i < m; i ++)
120         {
121             for(int j = 0; j < 4*n; j ++)
122             {
123                 if(g[i][j]=='1')
124                 {
125                     int cnt = 0;
126                     dfs2(i,j,cnt);
127                     if(cnt == 0)    result += 'W';
128                     else if(cnt==1) result += 'A';
129                     else if(cnt==2)    result += 'K';
130                     else if(cnt==3)    result += 'J';
131                     else if(cnt==4)    result += 'S';
132                     else if(cnt==5)    result += 'D';
133                 }
134             }
135         }
136         sort(result.begin(),result.end());
137         cout << "Case " << (++kase) << ": ";
138         cout << result << endl;
139     }
140     return 0;
141 }