UVA1103-Ancient Messages(脑洞+dfs)

Problem UVA1103-Ancient Messages

Accept: 1176 Submit: 6103

Time Limit: 3000 mSec

Problem Description

Input

Output

Sample Input

100 25 0000000000000000000000000

0000000000000000000000000

...(50 lines omitted)...

00001fe0000000000007c0000

00003fe0000000000007c0000

...(44 lines omitted)...

0000000000000000000000000

150 38

00000000000000000000000000000000000000

...(75 lines omitted)...

0000000003fffffffffffffffff00000000000

...(69 lines omitted)...

00000000000000000000000000000000000000

0 0

Sample output

Case 1: AKW

Case 2: AAAAA

题解：这个题重在脑洞，看出来联通块的个数与字母之间的关系的确不容易（我是没看出来）。开了脑洞之后问题就简单多了，先对最外面的白色区域dfs一下，然后就是dfs各个黑色区域，先把他们包围的联通块的范围划出来，然后计数里面的联通块个数，说的时候这划区域与计数是分开的，其实实现的时候是在一起的，划区域的时候如果碰到了白格，就停下来先对这个白格所在的联通块进行dfs，顺便记个数，区域划完了，计数也就搞定了

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <cstdlib>
  5 using namespace std;
  6 
  7 const int maxn = 200+5,maxm = 50+5;
  8 const int converse[16][4] =
  9 {
 10     {0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},
 11     {0,1,0,0},{0,1,0,1},{0,1,1,0},{0,1,1,1},
 12     {1,0,0,0},{1,0,0,1},{1,0,1,0},{1,0,1,1},
 13     {1,1,0,0},{1,1,0,1},{1,1,1,0},{1,1,1,1}
 14 };
 15 
 16 char gra[maxn][maxm];
 17 int buf[maxn][maxm<<2];
 18 int n,m,cnt;
 19 int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
 20 
 21 inline bool Judge(int x,int y){
 22     if(0<=x && 0<=y && x<n && y<m) return true;
 23     else return false;
 24 }
 25 
 26 void dfsw(int x,int y,int num){
 27     buf[x][y] = num;
 28     int xx,yy;
 29     for(int i = 0;i < 4;i++){
 30         xx = x+dir[i][0],yy = y+dir[i][1];
 31         if(Judge(xx,yy) && buf[xx][yy] == 0){
 32             dfsw(xx,yy,num);
 33         }
 34     }
 35 }
 36 
 37 void dfsn(int x,int y,int num){
 38     buf[x][y] = num;
 39     int xx,yy;
 40     for(int i = 0;i < 4;i++){
 41         xx = x+dir[i][0],yy = y+dir[i][1];
 42         if(Judge(xx,yy)){
 43             if(buf[xx][yy] == 1) dfsn(xx,yy,num);
 44             else if(buf[xx][yy] == 0){
 45                 cnt++;
 46                 dfsw(xx,yy,-1);
 47             }
 48         }
 49     }
 50 }
 51 
 52 void map_print(){
 53     for(int i = 0;i < n;i++){
 54         for(int j = 0;j < m;j++){
 55             printf("%d ",buf[i][j]);
 56         }
 57         printf("
");
 58     }
 59 }
 60 
 61 int sum[10];
 62 char q[10] = {'W','A','K','J','S','D'};
 63 int iCase = 1;
 64 
 65 int main()
 66 {
 67     //freopen("input.txt","r",stdin);
 68     //freopen("output.txt","w",stdout);
 69     while(~scanf("%d%d",&n,&m) && (n||m)){
 70         memset(buf,0,sizeof(buf));
 71         for(int i = 1;i <= n;i++){
 72             scanf("%s",gra[i]+1);
 73             for(int j = 1;j <= (int)strlen(gra[i]+1);j++){
 74                 int y = (j-1)<<2;
 75                 if('a'<=gra[i][j] && gra[i][j]<='z'){
 76                     for(int k = 0;k < 4;k++){
 77                         buf[i][y+k+1] = converse[gra[i][j]-'a'+10][k];
 78                     }
 79                 }
 80                 else{
 81                     for(int k = 0;k < 4;k++){
 82                         buf[i][y+k+1] = converse[gra[i][j]-'0'][k];
 83                     }
 84                 }
 85             }
 86         }
 87         n = n+2,m = 4*m+2;
 88         //map_print();
 89         dfsw(0,0,-1);
 90         int flag = 2;
 91         memset(sum,0,sizeof(sum));
 92         for(int i = 0;i < n;i++){
 93             for(int j = 0;j < m;j++){
 94                 if(buf[i][j] == 1){
 95                     cnt = 0;
 96                     dfsn(i,j,flag);
 97                     flag++;
 98                     sum[cnt]++;
 99                 }
100             }
101         }
102         //map_print();
103         printf("Case %d: ",iCase++);
104         if(sum[1] != 0) for(int i = 0;i < sum[1];i++) printf("%c",'A');
105         if(sum[5] != 0) for(int i = 0;i < sum[5];i++) printf("%c",'D');
106         if(sum[3] != 0) for(int i = 0;i < sum[3];i++) printf("%c",'J');
107         if(sum[2] != 0) for(int i = 0;i < sum[2];i++) printf("%c",'K');
108         if(sum[4] != 0) for(int i = 0;i < sum[4];i++) printf("%c",'S');
109         if(sum[0] != 0) for(int i = 0;i < sum[0];i++) printf("%c",'W');
110         printf("
");
111     }
112     return 0;
113 }