这题是2_1我最后一个A的题，也是2_1我觉得最难的题(就算不是最难，我也觉得是最烦的，一开始题意都不懂-_-!).我一开始不知道怎么去推到那扇墙，后来看了nocow的翻译，还有 NAROTOACM牛的提示，才知道点点意思，感觉可做，今天上午就献给它了。想法不算太难，就是我感觉好繁啊。 一开始还是推倒那扇墙出问题了，后来这里不出问题了，下标又越界了，再后来就是MLE了，最后用short过的。交了10+次。不过过了之后心情顿爽啊，哈哈。 官方版
  官方版
1 We use a simple recursive flood fill to number each room in the castle, and then look at all the pairs of rooms we can join by knocking out any wall. Since we're going to use the westernmost and then southernmost square, we need only consider knocking out walls to the north and to the east.
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <assert.h>
7
8#define MAXDIM 50
9#define MAXN 100
10#define MAXCOLOR 100
11#define MAXROOM (MAXDIM*MAXDIM)
12
13enum  {
14 Wwest = 1,
15 Wnorth = 2,
16 Weast = 4,
17 Wsouth = 8
18 };
19
20typedef struct Square Square;
21struct Square {
22 int wall;
23 int numbered;
24 int room;
25};
26
27int wid, ht;
28Square castle[MAXDIM][MAXDIM];
29int roomsize[MAXROOM];
30
31void
32number(int room, int x, int y)
33{
34 int w;
35
36  if(castle[x][y].numbered) {
37 assert(castle[x][y].room == room);
38 return;
39 }
40
41 castle[x][y].numbered = 1;
42 castle[x][y].room = room;
43 roomsize[room]++;
44
45 w = castle[x][y].wall;
46
47 if(x > 0 && !(w & Wwest))
48 number(room, x-1, y);
49
50 if(x+1 < wid && !(w & Weast))
51 number(room, x+1, y);
52
53 if(y > 0 && !(w & Wnorth))
54 number(room, x, y-1);
55
56 if(y+1 < ht && !(w & Wsouth))
57 number(room, x, y+1);
58}
59
60void
61main(void)
62{
63 FILE *fin, *fout;
64 int x, y, w, nroom, bigroom;
65 int i, n, m, mx, my;
66 char mc;
67
68 fin = fopen("castle.in", "r");
69 fout = fopen("castle.out", "w");
70 assert(fin != NULL && fout != NULL);
71
72 fscanf(fin, "%d %d", &wid, &ht);
73
74 /**//* read in wall info */
75 for(y=0; y<ht; y++) {
76 for(x=0; x<wid; x++) {
77 fscanf(fin, "%d", &w);
78 castle[x][y].wall = w;
79 }
80 }
81
82 /**//* number rooms */
83 nroom = 0;
84 for(y=0; y<ht; y++)
85 for(x=0; x<wid; x++)
86 if(!castle[x][y].numbered)
87 number(nroom++, x, y);
88
89 /**//* find biggest room */
90 bigroom = roomsize[0];
91 for(i=1; i<nroom; i++)
92 if(bigroom < roomsize[i])
93 bigroom = roomsize[i];
94
95 /**//* look at best that can come of removing an east or north wall */
96 m = 0;
97 for(x=0; x<wid; x++)
98 for(y=ht-1; y>=0; y--) {
99 if(y > 0 && castle[x][y].room != castle[x][y-1].room) {
100 n = roomsize[castle[x][y].room] + roomsize[castle[x][y-1].room];
101 if(n > m) {
102 m = n;
103 mx = x;
104 my = y;
105 mc = 'N';
106 }
107 }
108 if(x+1 < wid && castle[x][y].room != castle[x+1][y].room) {
109 n = roomsize[castle[x][y].room] + roomsize[castle[x+1][y].room];
110 if(n > m) {
111 m = n;
112 mx = x;
113 my = y;
114 mc = 'E';
115 }
116 }
117 }
118
119 fprintf(fout, "%d\n", nroom);
120 fprintf(fout, "%d\n", bigroom);
121 fprintf(fout, "%d\n", m);
122 fprintf(fout, "%d %d %c\n", my+1, mx+1, mc);
123 exit(0);
124}
125
126
|
|
常用链接
留言簿(1)
随笔分类(99)
随笔档案(71)
好友链接
搜索
最新评论
阅读排行榜
评论排行榜
|
|