题目不难，我用的BFS（），上网搜的时候，好像很多用的floodfill()，还是第一次听说，一会儿好好研究floodfill()
要注意的是选取房间移墙，应该是
choosing the wall farthest to the west (and then, if still tied, farthest to the south).
最开始，我理解成最远离西面，然后最远离南面。可怜我那 very poor 的英语。
正确的理解应该是最靠近西面，然后考虑最靠近南面的墙。
所以从最南往最北、最西往最东搜，就能得到题目所要求的解了。
My code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 | /* ID: tgh7281 LANG: C++ TASK: castle */ #include <iostream> #include <fstream> #include <queue> using namespace std; struct room { int count; //方格所在房间的编号 int area; //方格所在房间的面积 bool wall[4]; //n,e,s,w; //四个方向有无墙壁 bool visited; //方格是否被访问过 }; int dir[4][2]= { {0,-1},{-1,0},{0,1},{1,0} }; int cnt=0,s=0,maxs=0; int m,n; room flr[58][58]; void bfs(int i,int j); int main() { ifstream fin("castle.in"); ofstream fout("castle.out"); memset(flr,0,sizeof(flr)); fin>>m>>n; for (int i=1;i<=n;i++) //输入，并处理每个房间墙壁的情况 { for (int j=1;j<=m;j++) { int num; fin>>num; if (num>=8) flr[i][j].wall[3]=true,num-=8; if (num>=4) flr[i][j].wall[2]=true,num-=4; if (num>=2) flr[i][j].wall[1]=true,num-=2; if (num>=1) flr[i][j].wall[0]=true,num-=1; } } for (int i=1;i<=n;i++) { for (int j=1;j<=m;j++) { if (flr[i][j].visited) continue; cnt++; bfs(i,j); } } int newmax=0,maxx=0,maxy=0; char position; for (int j=1;j<=m;j++) { for (int i=n;i>=1;i–) { if (flr[i][j].wall[1]) //北墙存在 { if (flr[i][j].count!=flr[i-1][j].count) //不属于同一个房间 { if (flr[i][j].area+flr[i-1][j].area>newmax) { newmax=flr[i][j].area+flr[i-1][j].area; position='N'; maxy=j; maxx=i; } } } if (flr[i][j].wall[2]) //东墙存在 { if (flr[i][j].count!=flr[i][j+1].count) //不属于同一个房间 { if (flr[i][j].area+flr[i][j+1].area>newmax) { newmax=flr[i][j].area+flr[i][j+1].area; position='E'; maxy=j; maxx=i; } } } } } fout<<cnt<<endl; fout<<maxs<<endl; fout<<newmax<<endl; fout<<maxx<<' '<<maxy<<' '<<position<<endl; fin.close(); fout.close(); return 0; } void bfs(int i,int j) { queue<int> Q1,Q2; int x,y; flr[i][j].visited=true; Q1.push(i),Q1.push(j); Q2.push(i),Q2.push(j); s=1; //面积 while (!Q1.empty()) { i=Q1.front(); Q1.pop(); j=Q1.front(); Q1.pop(); for (int k=0;k<4;k++) { x=i+dir[k][0]; y=j+dir[k][1]; if (x>=1&&x<=n&&y>=1&&y<=m&&(!flr[x][y].visited)&&(!flr[i][j].wall[k])) { flr[x][y].visited=true; Q1.push(x),Q1.push(y); Q2.push(x),Q2.push(y); s++; } } } while (!Q2.empty()) { i=Q2.front(),Q2.pop(); j=Q2.front(),Q2.pop(); flr[i][j].count=cnt; flr[i][j].area=s; } maxs=max(maxs,s); } |
Code from usaco:
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <stdio.h> #include <stdlib.h> #include <string.h> #include <assert.h> #define MAXDIM 50 #define MAXN 100 #define MAXCOLOR 100 #define MAXROOM (MAXDIM*MAXDIM) enum { Wwest = 1, Wnorth = 2, Weast = 4, Wsouth = 8}; typedef struct Square Square; struct Square { int wall; int numbered; int room; }; int wid, ht; Square castle[MAXDIM][MAXDIM]; int roomsize[MAXROOM]; voidnumber(int room, int x, int y) { int w; if (castle[x][y].numbered) { assert(castle[x][y].room == room); return; } castle[x][y].numbered = 1; castle[x][y].room = room; roomsize[room]++; w = castle[x][y].wall; if (x > 0 && !(w & Wwest)) number(room, x-1, y); if (x+1 < wid && !(w & Weast)) number(room, x+1, y); if (y > 0 && !(w & Wnorth)) number(room, x, y-1); if (y+1 < ht && !(w & Wsouth)) number(room, x, y+1); } void main(void) { FILE *fin, *fout; int x, y, w, nroom, bigroom; int i, n, m, mx, my; char mc; fin = fopen("castle.in", "r"); fout = fopen("castle.out", "w"); assert(fin != NULL && fout != NULL); fscanf(fin, "%d %d", &wid, &ht); /* read in wall info */ for (y=0; y<ht; y++) { for (x=0; x<wid; x++) { fscanf(fin, "%d", &w); castle[x][y].wall = w; } } /* number rooms */ nroom = 0; for (y=0; y<ht; y++) for (x=0; x<wid; x++) if (!castle[x][y].numbered) number(nroom++, x, y); /* find biggest room */ bigroom = roomsize[0]; for (i=1; i<nroom; i++) if (bigroom < roomsize[i]) bigroom = roomsize[i]; /* look at best that can come of removing an east or north wall */ m = 0; for (x=0; x<wid; x++) for (y=ht-1; y>=0; y--) { if (y > 0 && castle[x][y].room != castle[x][y-1].room) { n = roomsize[castle[x][y].room] + roomsize[castle[x][y-1].room]; if (n > m) { m = n; mx = x; my = y; mc = 'N'; } } if (x+1 < wid && castle[x][y].room != castle[x+1][y].room) { n = roomsize[castle[x][y].room] + roomsize[castle[x+1][y].room]; if (n > m) { m = n; mx = x; my = y; mc = 'E'; } } } fprintf(fout, "%d\n", nroom); fprintf(fout, "%d\n", bigroom); fprintf(fout, "%d\n", m); fprintf(fout, "%d %d %c\n", my+1, mx+1, mc); exit(0); } |
1,582 views