| 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) |
|
| ???? |
|
| 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) |
|
| ???? |
|
| 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;
??}
};