這題是2_1我最后一個(gè)A的題，也是2_1我覺(jué)得最難的題(就算不是最難，我也覺(jué)得是最煩的，一開(kāi)始題意都不懂-_-!).我一開(kāi)始不知道怎么去推到那扇墻，后來(lái)看了nocow的翻譯，還有 NAROTOACM牛的提示，才知道點(diǎn)點(diǎn)意思，感覺(jué)可做，今天上午就獻(xiàn)給它了。想法不算太難，就是我感覺(jué)好繁啊。 一開(kāi)始還是推倒那扇墻出問(wèn)題了，后來(lái)這里不出問(wèn)題了，下標(biāo)又越界了，再后來(lái)就是MLE了，最后用short過(guò)的。交了10+次。不過(guò)過(guò)了之后心情頓爽啊，哈哈。 官方版
  官方版
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
|