timus_1006

正方形框

　　这道题目比较有意思，它在屏幕上给出了一张画有一些正方形方框的图形，这些方框可能互相覆盖，但不会超出屏幕的边界。现有要求你给出一个能构成该图形的方框序列。这些方框可以由下列字符组成：

　　输入：一张画有正方形框的图

　　输出：

　　K
　　X₁ Y₁ A₁
　　…
　　X_k Y_k A_k

　　K代表正方框的数量，X和Y代表正方形的左上角坐标，A代表正方形的长度

　　样例输入：

　　样例输出：

  1 #include <stdio.h>
  2 
  3 unsigned char map[50][20];//记录屏幕中框的情况
  4 unsigned char screen[20][50];
  5 typedef struct _frame_t
  6 {
  7     int left;//左上角的横坐标
  8     int top;//左上角的纵坐标
  9     int width;//宽度
 10 }frame_t;
 11 
 12 #define MAX_FRAME_SIZE 2000
 13 #define min(a, b) (a > b ? b : a)
 14 frame_t frame[MAX_FRAME_SIZE + 1]; 
 15 int n;
 16 
 17 #define MAX_FRAME 16
 18 
 19 //#define DEBUG 
 20 #ifdef DEBUG
 21 #define PRINT() Print()
 22 #else 
 23 #define PRINT()
 24 #endif
 25 
 26 void Print()
 27 {
 28     int i, j;
 29 
 30     for (i = 0; i < 20; i ++)
 31     {
 32         for (j = 0; j < 50; j ++)
 33                 printf("%c ", (map[j][i] ? map[j][i] : '1'));
 34         printf("\n");
 35     }
 36     printf("\n");
 37 }
 38 int IsFrame(int left, int top, int len)
 39 {
 40     int i;
 41 
 42     for (i = 1; i < len - 1; i ++)
 43     {
 44         if (!(map[left + i][top] == 196 || map[left + i][top] == 0))    
 45             return 0;
 46         if (!(map[left + i][top + len - 1] == 196 || map[left + i][top + len - 1] == 0))
 47             return 0;
 48         if (!(map[left][top + i] == 179 || map[left][top + i] == 0))
 49             return 0;
 50         if (!(map[left + len - 1][top + i] == 179 || map[left + len - 1][top + i] == 0))
 51             return 0;
 52     }
 53     if (!(map[left][top] == 218 || map[left][top] == 0))
 54         return 0;
 55     if (!(map[left + len - 1][top] == 191 || map[left + len - 1][top] == 0))
 56         return 0;
 57     if (!(map[left][top + len - 1] == 192 || map[left][top + len - 1] == 0))
 58         return 0;
 59     if (!(map[left + len - 1][top + len - 1] == 217 || map[left + len - 1][top + len - 1] == 0))
 60         return 0;
 61     return 1;
 62 }
 63 void ReduceFrame(int left, int top, int width)
 64 {
 65     int i;
 66 
 67     for (i = 0; i < width; i ++)
 68         map[left][top + i] = map[left + i][top] = map[left + width - 1][top + i] = map[left + i][top + width - 1] = 0;
 69 }
 70 
 71 int Search(int left, int top)
 72 {
 73     int i, j, len, count = 0;
 74     frame_t temp;
 75 
 76     if (map[left][top] == 196)        
 77     {
 78         //─
 79         i = 1;
 80         while (i < MAX_FRAME && left - i >= 0 && map[left - i][top] != 46)
 81         {
 82             len = min(MAX_FRAME , min(50 - (left - i), 20 - top));    
 83             while (len >= 2)
 84             {
 85                 if (IsFrame(left - i, top, len))
 86                 {
 87                     ReduceFrame(left - i, top, len);    
 88                     frame[n].left = left - i;
 89                     frame[n].top = top;
 90                     frame[n ++].width = len;
 91                     PRINT();
 92                     return 1;
 93                 }
 94                 len --;
 95             }
 96             len = min(MAX_FRAME, min(50 - (left - i), top + 1));    
 97             while (len >= 2)
 98             {
 99                 if (IsFrame(left - i, top - len + 1, len))    
100                 {
101                     ReduceFrame(left - i, top - len + 1, len);    
102                     frame[n].left = left - i;
103                     frame[n].top = top - len + 1;
104                     frame[n ++ ].width = len;
105                     PRINT();
106                     return 1;
107                 }
108                 len --;
109             }
110             i ++;
111         }
112     }
113     else if (map[left][top] == 179)
114     {
115         //│    
116         i = 1;
117         while (i <  MAX_FRAME && top - i >= 0 && map[left][top - i] != 46)
118         {
119             len = min(MAX_FRAME , min(50 - left, 20 - (top - i)));    
120             while (len >= 2)
121             {
122                 if (IsFrame(left, top - i, len))
123                 {
124                     ReduceFrame(left, top - i, len);    
125                     frame[n].left = left;
126                     frame[n].top = top - i;
127                     frame[n ++].width = len;
128                     PRINT();
129                     return 1;
130                 }
131                 len --;
132             }
133             len = min(MAX_FRAME , min(left + 1, 20 - (top - i)));    
134             while (len >= 2)
135             {
136                 if (IsFrame(left - len + 1, top - i, len))
137                 {
138                     ReduceFrame(left - len + 1, top - i, len);    
139                     frame[n].left = left - len + 1;
140                     frame[n].top = top - i;
141                     frame[n ++].width = len;
142                     PRINT();
143                     return 1;
144                 }
145                 len --;
146             }
147             i ++;
148         }
149     }
150     else if (map[left][top] == 218)
151     {
152         //┌
153         len = min(MAX_FRAME , min(50 - left, 20 - top));    
154         while (len >= 2)
155         {
156             if (IsFrame(left, top, len))
157             {
158                 ReduceFrame(left, top, len);    
159                 frame[n].left = left;
160                 frame[n].top = top;
161                 frame[n ++].width = len;
162                 PRINT();
163                 return 1;
164             }
165             len --;
166         }
167     }
168     else if (map[left][top] == 191)
169     {
170         //┐
171         len = min(MAX_FRAME , min(left + 1, 20 - top));    
172         while (len >= 2)
173         {
174             if (IsFrame(left - len + 1, top, len))
175             {
176                 ReduceFrame(left - len + 1, top, len);    
177                 frame[n].left = left - len + 1;
178                 frame[n].top = top;
179                 frame[n ++].width = len;
180                 PRINT();
181                 return 1;
182             }
183             len --;
184         }
185     }
186     else if (map[left][top] == 217)
187     {
188         //┘
189         len = min(MAX_FRAME, min(left + 1, top + 1));    
190         while (len >= 2)
191         {
192             if (IsFrame(left - len + 1, top - len + 1, len))    
193             {
194                 ReduceFrame(left - len + 1, top - len + 1, len);    
195                 frame[n].left = left - len + 1;
196                 frame[n].top = top - len + 1;
197                 frame[n ++ ].width = len;
198                 PRINT();
199                 return 1;
200             }
201             len --;
202         }
203 
204     }
205     else
206     {
207         //└    
208         len = min(MAX_FRAME, min(50 - left, top + 1));    
209         while (len >= 2)
210         {
211             if (IsFrame(left, top - len + 1, len))    
212             {
213                 ReduceFrame(left, top - len + 1, len);    
214                 frame[n].left = left;
215                 frame[n].top = top - len + 1;
216                 frame[n ++ ].width = len;
217                 PRINT();
218                 return 1;
219             }
220             len --;
221         }
222     }
223     return 0;
224 }
225 int main(void)
226 {
227     int i,j;
228     //输入数据
229     for (i = 0; i < 20; i ++)
230             scanf("%s", screen[i]);    
231     for (i = 0; i < 20; i ++)
232         for (j = 0; j < 50; j ++)
233             map[j][i] = screen[i][j];
234     PRINT();
235 begin:
236     for (j = 0; j < 20; j ++)
237         for (i = 0; i < 50; i ++)
238             if (!(map[i][j] == 46 || map[i][j] == 0 || map[i][j] == 196 || map[i][j] == 179) && Search(i, j))
239                 goto begin;
240 begin1:
241     for (j = 0; j < 20; j ++)
242         for (i = 0; i < 50; i ++)
243             if (!(map[i][j] == 46 || map[i][j] == 0) && Search(i, j))
244                 goto begin1;
245     printf("%d\n", n);
246     for (i = n - 1; i >= 0; i --)
247         printf("%d %d %d\n", frame[i].left, frame[i].top, frame[i].width);
248     return 0;
249 }

　　程序的大概思路就是总是扫描屏幕，每次扫描都找到一个屏幕上最上面的方框，将它保持起来并从屏幕上删除这个方框，重复这个过程直到屏幕上没有了方框为止。程序235-239行是对扫描屏幕中方框的顶点，如果顶点所在的方框在最上面，就将这个方框直接保存起来，并且从新扫描这个屏幕，这样这个方框下面的被遮盖的方框就可以找出来了。第240-244行对应的是扫描屏幕中方框的边，如果边所在的方框在最上面，就将这个方框直接保存起来，并且从新扫描这个屏幕。第245-247行输出结果。Search函数主要是用来构造方框的顶点，这是对于不确定方框顶点的情况，或者是构造方框的长度，这是已经确定了方框的顶点的情况。IsFrame判断Search构造的方框是否是当前屏幕最上方的方框。ReduceFrame是用来去除屏幕中已经找到的方框。