superman

聚精会神搞建设 一心一意谋发展
posts - 190, comments - 17, trackbacks - 0, articles - 0
   :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Section 2.1 - The Castle

Posted on 2009-03-25 11:22 superman 阅读(114) 评论(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, 255sizeof(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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理