oyjpArt ACM/ICPC算法程序设计空间

Problem Statement for LandAndSea

Problem Statement      Bob's father bought him a toy map of islands and seas. The map is a two-dimensional grid where each cell is either 'x' or '.'. A sea is defined as a maximal connected group of '.' cells, where two '.' cells are connected if they are vertically or horizontally adjacent. An island is defined as a maximal connected group of 'x' cells, where two 'x' cells are connected if they are vertically, horizontally, or diagonally adjacent. An island has a level of 0 if it contains no other islands. An island has a level of K+1 if it contains one or more islands and the highest level of a contained island is K. An island A contains island B if A and B are different and, if you start sailing from any point of island B, you won't be able to sail out of island A (you can sail only horizontally and vertically, but not diagonally). For example, the given map below has 5 islands with level 0 (islands 0 - 4 on the right picture) and one island with level 1 (island 5). Please note that starting at island 3, you can not sail outside island 5 (you can not sail diagonally), but its possible get out of island 1 when starting at island 4. xxx.x...xxxxx 000.0...11111 xxxx....x...x 0000....1...1 ........x.x.x ........1.4.1 ..xxxxx.x...x ..55555.1...1 ..x...x.xxx.x ..5...5.111.1 ..x.x.x...x.. ..5.3.5...1.. ..x...x...xxx ..5...5...111 ...xxxxxx.... ...555555.... x............ 2............ Given a String[] seaMap, return a int[], where the k-th element is the number of islands of level k. The int[] must contain exactly (m + 1) elements, where m is the highest level of an island in the map.   Definition      Class: LandAndSea Method: howManyIslands Parameters: String[] Returns: int[] Method signature: int[] howManyIslands(String[] seaMap) (be sure your method is public)        Constraints - seaMap will contain between 1 and 50 elements, inclusive. - Each element of seaMap will contain between 1 and 50 characters, inclusive. - Each element of seaMap will contain the same number of characters. - Each element of seaMap will contain only '.' and lowercase 'x' characters.   Examples 0)      {"x"} Returns: {1 } 1)      { "xxxxx", "x...x", "x.x.x", "x...x", "xxxxx" } Returns: {1, 1 } 2)      { "xxxxx", "x...x", "x.x.x", "x...x", "xxxxx", "xxxxx", "x...x", "x.x.x", "x...x", "xxxxx" } Returns: {2, 1 } 3)      { "..", ".." } Returns: { } 4)      { "............", ".......xxxx.", "..xxx.x...x.", "..x..x..x.x.", "..x.x.x...x.", "..xx...xxx.." } Returns: {1, 1 }

TopCoder 官方Solution
我觉得够创意~
LandAndSea  
Used as: Division Two - Level Three:

Value	1050
Submission Rate	26 / 694 (3.75%)
Success Rate	1 / 26 (3.85%)
High Score	vanessa for 457.68 points (48 mins 19 secs)
Average Score	457.68 (for 1 correct submission)

Used as: Division One - Level Two:

Value	550
Submission Rate	250 / 544 (45.96%)
Success Rate	73 / 250 (29.20%)
High Score	gozman for 359.52 points (23 mins 28 secs)
Average Score	250.35 (for 73 correct submissions)

The solution can be split into two parts - generating a tree with nodes considered as  islands and seas and finding the number of islands of each level. In generating a tree, we will add covering waters '.' as the boundary of the map. We use the flood fill to find all seas and islands. The sea connected with the boundary element is defined as the root of the tree. From each visited sea we will visit unvisisted islands if they have at least one element vertically or horizontally adjacent to any element of the sea. From each visited island we will visit unvisisted seas if they have at least one element vertically, horizontally, or diagonally adjacent to any element of the island.

                    ...............000000000000000
xxx.x...xxxxx       .xxx.x...xxxxx.011101000222220
xxxx....x...x       .xxxx....x...x.011110000200020
........x.x.x       .........x.x.x.000000000203020
..xxxxx.x...x       ...xxxxx.x...x.000444440200020
..x...x.xxx.x   ->  ...x...x.xxx.x.000466640222020
..x.x.x...x..       ...x.x.x...x...000467640002000
..x...x...xxx       ...x...x...xxx.000466640002220
...xxxxxx....       ....xxxxxx.....000044444400000
x............       .x.............050000000000000
...............                    000000000000000

In the picture above, connected groups 0 and 6 are seas and connected groups are islands. The root 0 has children 1, 2, 3, 4, 5. The node 4 has a child 6(a sea). The sea 6 has a child 7(an island).

After creating the tree, it is easy to find the number of islands of each level as following. Any island or sea that have no child will be defined as level 1 and 0, respectively. The level of each island is defined as the maximum level of all its own children plus 1 and the level of each sea is defined as the maximum level of all its own children.
下面是官方提供的参赛者的code：
#include <iostream>
#include <sstream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <memory>
#include <cctype>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <deque>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
using namespace std;

typedef long long Int;
typedef pair<int,int> PII;
typedef vector<int> VInt;

#define FOR(i, a, b) for(i = a; i < b; i++)
#define RFOR(i, a, b) for(i = a - 1; i >= b; i--)
#define CLEAR(a, b) memset(a, b, sizeof(a))
#define COPY(a, b) memcpy(a, b, sizeof(a))
#define SIZE(a) int((a).size()) 
#define ALL(a) (a).begin(),(a).end() 
#define FOREACH(i, a) for(i = (a).begin(); i != (a).end(); i++) 
#define PB push_back
#define MP make_pair

vector<string> A;
int B[64][64];
int N, M;

int DX[] = {1, -1, 0, 0, 1, 1, -1, -1};
int DY[] = {0, 0, 1, -1, 1, -1, 1, -1};

void dfs(int x, int y, queue<PII>& Q)
{
  B[x][y] = 1;
  int i;
  int finish = A[x][y] == '.' ? 4 : 8;
  FOR(i, 0, finish)
  {
    int xx = x + DX[i];
    int yy = y + DY[i];

    if(xx < 0 || xx >= N || yy < 0 || yy >= M || B[xx][yy])
      continue;

    if(A[x][y] == A[xx][yy])
      dfs(xx, yy, Q);
    else
      Q.push(PII(xx, yy));
  }
}

class LandAndSea {
  VInt Res;

  int F(int x, int y)
  {
    queue<PII> Q;
    dfs(x, y, Q);

    int res = -1;
    while(!Q.empty())
    {
      int xx = Q.front().first;
      int yy = Q.front().second;
      Q.pop();
      if(B[xx][yy] == 0)
        res = max(res, F(xx, yy));
    }

    if(A[x][y] != '.')
    {
      res++;
      while(SIZE(Res) <= res)
        Res.PB(0);

      Res[res]++;
    }

    return res;
  }

  public:
  vector <int> howManyIslands(vector <string> seaMap) {
    N = SIZE(seaMap);
    M = SIZE(seaMap[0]);
    int i;
    FOR(i, 0, N)
      seaMap[i] = "." + seaMap[i] + ".";

    seaMap.insert(seaMap.begin(), string(M + 2, '.'));
    seaMap.PB(string(M + 2, '.'));

    N += 2;
    M += 2;

    Res.clear();
    A = seaMap;
    CLEAR(B, 0);
    F(0, 0);

    return Res;
  }
};