UVA - 1103 Ancient Messages-白红宇

UVA - 1103 Ancient Messages

阅读量：5047 次

发布时间：2019-06-12

本文共 5490 字，大约阅读时间需要 18 分钟。

题意：给定一个图像，字典序输出里面对应的象形文字。

分析：把由十六进制构成的图转换成二进制的图，就能很容易理解题意。

1、在最外圈加一圈0，便于使所有象形文字外的0都是连通的

2、将所有连通的0和1都标号（dfs）

3、再查象形文字里的洞的个数，把所有1附近的不是外圈的0都set一下就好了。

#pragma comment(linker, "/STACK:102400000, 102400000")#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   #include
                   
                    #include
                    
                     #include
                     
                      #define Min(a, b) ((a < b) ? a : b)#define Max(a, b) ((a < b) ? b : a)typedef long long ll;typedef unsigned long long llu;const int INT_INF = 0x3f3f3f3f;const int INT_M_INF = 0x7f7f7f7f;const ll LL_INF = 0x3f3f3f3f3f3f3f3f;const ll LL_M_INF = 0x7f7f7f7f7f7f7f7f;const int dr[] = { 0, 0, -1, 1, -1, -1, 1, 1};const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};const int MOD = 1e9 + 7;const double pi = acos(-1.0);const double eps = 1e-8;const int MAXN = 200 + 10;const int MAXT = 50 + 10;using namespace std;char pic[MAXN][MAXT << 2];int vis[MAXN][MAXT << 2];char s[MAXN];map
                      
                        mp;map
                       
                         ma;set
                        
                          in[44100];//连通块1里的洞的个数,set去重vector
                         
                           y;//由1组成的连通块的标号vector
                          
                            ans;int cnt, H, W;;void init(){ //十六进制与二进制映射 string a = "0123456789abcdef"; string b = "0000000100100011010001010110011110001001101010111100110111101111"; int len = a.size(); int st = 0; for(int i = 0; i < len; ++i){ mp[a[i]] = b.substr(st, 4);//从st开始取4个 st += 4; } string tmp = "WAKJSD"; for(int i = 0; i < 6; ++i){ ma[i] = tmp[i]; }}bool judge(int x, int y){ return x >= 0 && x <= H + 1 && y >= 0 && y <= 4 * W + 1;}void dfs(int x, int y){ vis[x][y] = cnt; for(int i = 0; i < 4; ++i){ //题意中other black pixel on its top, bottom, left, or right side int tmpx = x + dr[i]; int tmpy = y + dc[i]; if(judge(tmpx, tmpy) && !vis[tmpx][tmpy] && pic[tmpx][tmpy] == pic[x][y]){ dfs(tmpx, tmpy); } }}int main(){ init(); int cases = 0; while(scanf("%d%d", &H, &W) == 2){ if(!H && !W) return 0; memset(pic, '0', sizeof pic); memset(vis, 0, sizeof vis); for(int i = 0; i < 44100; ++i){ in[i].clear(); } y.clear(); ans.clear(); for(int i = 1; i <= H; ++i){ scanf("%s", s); string ans = ""; for(int j = 0; j < W; ++j){ ans += mp[s[j]]; } for(int j = 1; j <= 4 * W; ++j){ pic[i][j] = ans[j - 1]; } } cnt = 0;//为每一个连通块标号 for(int i = 0; i < H + 2; ++i){ for(int j = 0; j < 4 * W + 2; ++j){ if(!vis[i][j]){ ++cnt; dfs(i, j); if(pic[i][j] == '1') y.push_back(cnt); } } } for(int i = 0; i < H + 2; ++i){ for(int j = 0; j < 4 * W + 2; ++j){ if(pic[i][j] == '1'){ for(int k = 0; k < 4; ++k){ int tmpx = i + dr[k]; int tmpy = j + dc[k]; if(judge(tmpx, tmpy) && pic[tmpx][tmpy] == '0' && vis[tmpx][tmpy] != 1){ //象形文字里的0 in[vis[i][j]].insert(vis[tmpx][tmpy]); } } } } } int len = y.size(); for(int i = 0; i < len; ++i){ ans.push_back(ma[in[y[i]].size()]); } sort(ans.begin(), ans.end()); len = ans.size(); printf("Case %d: ", ++cases); for(int i = 0; i < len; ++i){ printf("%c", ans[i]); } printf("\n"); } return 0;}

一组完整的测试样例：

100 2500000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000f800000000000000000000001fe00000000000000000000007ff00000000000000000000007ff8000000000000000000000f8f8000000000000000000001f07c000000000000000000001e03c000000000018000000001e01c00000000003c000000001c01c00000000007c000000003c01e0000000000f8000000003c01e0000000001f0000000001c01c0000000003f0000000001c01c0000000007e0000000001e01c000000000fc0000000001e03c000000001fc0000000000e03c000000001fc0000000000f038000000003ff0000000000f078000000003ff80000000007870000000007ff800000000038f0000000007cfc0000000003ce0000000007c7c0000000781fc0f0000000f87c00000007ffffff0000000f07c00000007ffffff0000000f07c00000007ffffff0000001f07c00000007ffffff0000000e03e00000007fcf81f0000000603e0000000000f8000000000003e0000000000f8000000000003e0000000000f8000000000003e0000000000f8000000000001e0000000000f8000000000001f0000000000fc000000000001f0000000000fc000000000001f0000000000fc000000000001f0000000000fc000000000000f0000000001fc000000000000f8000000001fc000000000000f8000000001fc000000000000f8000000001fc000000000000f8000000001fe000000000000f8000000001fe00000000000078000000001fe0000000000007c000000001fe0000000000007c000000003fe0000000000007c000000003fe0000000000007c000000003fe0000000000007c000000003fe0000c00000003c000000000000003ff0000003c000000000000007ff8000003e00000000000001fffc000003e00000000000003e03f000003e00000000000007c00f000003e0000000000000f0003800003f0000000000000e0001c00003fc000000000001c0001e00007fe000000000003c0000e0000fff000000000073c000070000fdf0000000001ff8000070001f0f8000000001ff8000070001e078000000003cf0000078001e038000000003870000033001e03800000000307800003fc01e03800000000703800007fe00e03800000000703800007ce00e03800000000703c000078700703800000000701e0000f0700701000000000701e0000e0700300000000000700f0001c07000000000000006007800380600000000000000e003e00700600000000000000e001fe7e00600000000000000e000fffc00e00000000000000e0000ff000e00000000000000f800038000e00000000000000fff0000000e00000000000000fffff00000e0000000000000003ffffe000c000000000000000007ffffc0c00000000000000000007ffffc000000000000000000000fffc00000000000000000000001fc00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

输出：AKW

转载于:https://www.cnblogs.com/tyty-Somnuspoppy/p/6272593.html

你可能感兴趣的文章

luogu4849 寻找宝藏 (cdq分治+dp)

查看>>

Spring Cloud微服务笔记（五）Feign

查看>>

C语言键盘按键列表