• <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 閱讀(1293) 評論(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;
            ??}
            };
            7国产欧美日韩综合天堂中文久久久久 | 精品久久久无码中文字幕| 色综合合久久天天综合绕视看| 久久人人爽人人爽人人片AV东京热| 性高湖久久久久久久久AAAAA| 亚洲精品无码久久一线| 99热成人精品免费久久| 一本色道久久88综合日韩精品 | 热re99久久精品国产99热| 久久99精品国产麻豆蜜芽| 亚洲国产精品18久久久久久| 国产精品成人99久久久久 | 伊人久久大香线蕉av不变影院| 精品久久久久久中文字幕| 欧美亚洲国产精品久久久久| 亚洲一区二区三区日本久久九| 噜噜噜色噜噜噜久久| 99久久精品国产一区二区| 久久久久亚洲av无码专区喷水 | 7777久久久国产精品消防器材| 99热精品久久只有精品| 久久99国产精品尤物| 狠狠色综合网站久久久久久久高清| 国产精品日韩深夜福利久久| 国产韩国精品一区二区三区久久| 国产A级毛片久久久精品毛片| 久久www免费人成精品香蕉| 久久免费视频观看| 国产精品久久久久久一区二区三区| 欧美亚洲国产精品久久久久| 香蕉99久久国产综合精品宅男自| 99久久精品免费| 国産精品久久久久久久| 国产成人综合久久精品尤物| 国产精品九九久久精品女同亚洲欧美日韩综合区 | 久久国产热这里只有精品| 99热都是精品久久久久久| 国产女人aaa级久久久级| 久久久久噜噜噜亚洲熟女综合 | 久久se精品一区精品二区| 91精品国产高清91久久久久久|