Categories

USACO 2.1.1 The Castle

题目不难,我用的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);
}

Leave a Reply

You can use these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

  

  

  

*