• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            TopCoder SRM341 LandAndSea

            Posted on 2007-03-17 20:02 oyjpart 閱讀(1291) 評論(0)  編輯 收藏 引用 所屬分類: 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:
            Value1050
            Submission Rate26 / 694 (3.75%)
            Success Rate1 / 26 (3.85%)
            High Scorevanessa for 457.68 points (48 mins 19 secs)
            Average Score457.68 (for 1 correct submission)
            Used as: Division One - Level Two:
            Value550
            Submission Rate250 / 544 (45.96%)
            Success Rate73 / 250 (29.20%)
            High Scoregozman for 359.52 points (23 mins 28 secs)
            Average Score250.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;
            ??}
            };
            国内精品久久国产| 亚洲va国产va天堂va久久| 蜜臀av性久久久久蜜臀aⅴ| 午夜精品久久久久成人| 91久久精品国产91性色也| 91久久精一区二区三区大全| 久久精品久久久久观看99水蜜桃| 精品久久久久久无码免费| 精品久久一区二区| 久久777国产线看观看精品| 久久国产精品国产自线拍免费| 婷婷综合久久中文字幕蜜桃三电影 | 色99久久久久高潮综合影院| 97精品国产97久久久久久免费 | 久久99精品久久久久久9蜜桃| 久久99国产精一区二区三区| 狠狠干狠狠久久| 久久精品国产一区二区电影| 99久久www免费人成精品| 久久久WWW成人免费精品| 欧美久久久久久午夜精品| 亚洲七七久久精品中文国产| 久久中文字幕人妻丝袜| 亚洲国产精品无码久久一区二区| 久久99久国产麻精品66| 日韩乱码人妻无码中文字幕久久 | 国产精品日韩欧美久久综合| 久久久久亚洲AV成人网人人软件| 日韩影院久久| 日产精品久久久久久久性色| 狠狠色丁香久久综合婷婷| 色天使久久综合网天天| 久久成人国产精品| 久久夜色精品国产www| 无码国内精品久久人妻蜜桃 | 久久亚洲国产成人精品性色| 伊人久久综合热线大杳蕉下载| 久久99精品国产麻豆婷婷| 久久人人爽人人爽人人片av高请 | 2021国产精品久久精品| 久久久久久夜精品精品免费啦|