Posted on 2009-03-25 11:22
superman 閱讀(117)
評論(0) 編輯 收藏 引用 所屬分類:
USACO
1 #include <iostream>
2
3 using namespace std;
4
5 int n, m;
6 int castleStructure[50][50];
7 int castleRegion[50][50];
8
9 int regionCnt;
10 int areaOfRegions[2500];
11
12 void getRegion(int i, int j)
13 {
14 if (castleRegion[i][j] != -1)
15 return;
16 castleRegion[i][j] = regionCnt;
17 if ((castleStructure[i][j] & 1) == 0) //W
18 getRegion(i, j - 1);
19 if ((castleStructure[i][j] & 2) == 0) //N
20 getRegion(i - 1, j);
21 if ((castleStructure[i][j] & 4) == 0) //E
22 getRegion(i, j + 1);
23 if ((castleStructure[i][j] & 8) == 0) //S
24 getRegion(i + 1, j);
25 }
26
27 int main()
28 {
29 freopen("castle.in", "r", stdin);
30 freopen("castle.out", "w", stdout);
31
32 cin >> m >> n;
33 for (int i = 0; i < n; i++)
34 for (int j = 0; j < m; j++)
35 cin >> castleStructure[i][j];
36
37 memset(castleRegion, 255, sizeof(castleRegion));
38
39 for (int i = 0; i < n; i++)
40 for (int j = 0; j < m; j++)
41 if (castleRegion[i][j] == -1)
42 {
43 getRegion(i, j);
44 regionCnt++;
45 }
46
47 //ans 1
48 cout << regionCnt << endl;
49
50 for (int i = 0; i < n; i++)
51 for (int j = 0; j < m; j++)
52 areaOfRegions[castleRegion[i][j]]++;
53
54 int maxAreaOfRegions = 0;
55 for (int i = 0; i < regionCnt; i++)
56 maxAreaOfRegions >?= areaOfRegions[i];
57
58 //ans 2
59 cout << maxAreaOfRegions << endl;
60
61 int maxAreaAfterRemoveOneWall = 0;
62 struct { int x, y, dir; } theWallToRemove;
63
64 for (int j = 0; j < m; j++)
65 for (int i = n - 1; i >= 0; i--)
66 {
67 if ((castleStructure[i][j] & 1) == 1 && j - 1 >= 0) //W
68 {
69 if (castleRegion[i][j] == castleRegion[i][j - 1])
70 continue;
71 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i][j - 1]];
72 if (t > maxAreaAfterRemoveOneWall)
73 {
74 maxAreaAfterRemoveOneWall = t;
75 theWallToRemove.x = i;
76 theWallToRemove.y = j;
77 theWallToRemove.dir = 1;
78 }
79 }
80 if ((castleStructure[i][j] & 2) == 2 && i - 1 >= 0) //N
81 {
82 if (castleRegion[i][j] == castleRegion[i - 1][j])
83 continue;
84 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i - 1][j]];
85 if (t > maxAreaAfterRemoveOneWall)
86 {
87 maxAreaAfterRemoveOneWall = t;
88 theWallToRemove.x = i;
89 theWallToRemove.y = j;
90 theWallToRemove.dir = 2;
91 }
92 }
93 if ((castleStructure[i][j] & 4) == 4 && j + 1 < m) //E
94 {
95 if (castleRegion[i][j] == castleRegion[i][j + 1])
96 continue;
97 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i][j + 1]];
98 if (t > maxAreaAfterRemoveOneWall)
99 {
100 maxAreaAfterRemoveOneWall = t;
101 theWallToRemove.x = i;
102 theWallToRemove.y = j;
103 theWallToRemove.dir = 4;
104 }
105 }
106 if ((castleStructure[i][j] & 8) == 8 && i + 1 < n) //S
107 {
108 if (castleRegion[i][j] == castleRegion[i + 1][j])
109 continue;
110 int t = areaOfRegions[castleRegion[i][j]] + areaOfRegions[castleRegion[i + 1][j]];
111 if (t > maxAreaAfterRemoveOneWall)
112 {
113 maxAreaAfterRemoveOneWall = t;
114 theWallToRemove.x = i;
115 theWallToRemove.y = j;
116 theWallToRemove.dir = 8;
117 }
118 }
119 }
120
121 //ans 3
122 cout << maxAreaAfterRemoveOneWall << endl;
123 cout << theWallToRemove.x + 1 << ' '
124 << theWallToRemove.y + 1 << ' ';
125 if (theWallToRemove.dir == 1) cout << 'W' << endl;
126 if (theWallToRemove.dir == 2) cout << 'N' << endl;
127 if (theWallToRemove.dir == 4) cout << 'E' << endl;
128 if (theWallToRemove.dir == 8) cout << 'S' << endl;
129
130 return 0;
131 }
132