這題是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)
好友鏈接
搜索
最新評論
閱讀排行榜
評論排行榜
|
|