• <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>

            USACO 2.1.1 The Castle 分析及代碼

            The Castle
            IOI'94 - Day 1

            In a stroke of luck almost beyond imagination, Farmer John was sent a ticket to the Irish Sweepstakes (really a lottery) for his birthday. This ticket turned out to have only the winning number for the lottery! Farmer John won a fabulous castle in the Irish countryside.

            Bragging rights being what they are in Wisconsin, Farmer John wished to tell his cows all about the castle. He wanted to know how many rooms it has and how big the largest room was. In fact, he wants to take out a single wall to make an even bigger room.

            Your task is to help Farmer John know the exact room count and sizes.

            The castle floorplan is divided into M (wide) by N (1 <=M,N<=50) square modules. Each such module can have between zero and four walls. Castles always have walls on their "outer edges" to keep out the wind and rain.

            Consider this annotated floorplan of a castle:

                 1   2   3   4   5   6   7
              #############################
            1 #   |   #   |   #   |   |   #
              #####---#####---#---#####---#
            2 #   #   |   #   #   #   #   #
              #---#####---#####---#####---#
            3 #   |   |   #   #   #   #   #
              #---#########---#####---#---#
            4 # ->#   |   |   |   |   #   #
              #############################
            #  = Wall     -,|  = No wall
            -> = Points to the wall to remove to
            make the largest possible new room
            

            By way of example, this castle sits on a 7 x 4 base. A "room" includes any set of connected "squares" in the floor plan. This floorplan contains five rooms (whose sizes are 9, 7, 3, 1, and 8 in no particular order).

            Removing the wall marked by the arrow merges a pair of rooms to make the largest possible room that can be made by removing a single wall.

            The castle always has at least two rooms and always has a wall that can be removed.

            PROGRAM NAME: castle

            INPUT FORMAT

            The map is stored in the form of numbers, one number for each module, M numbers on each of N lines to describe the floorplan. The input order corresponds to the numbering in the example diagram above.

            Each module number tells how many of the four walls exist and is the sum of up to four integers:

            • 1: wall to the west
            • 2: wall to the north
            • 4: wall to the east
            • 8: wall to the south

            Inner walls are defined twice; a wall to the south in module 1,1 is also indicated as a wall to the north in module 2,1.
            Line 1: Two space-separated integers: M and N
            Line 2..: M x N integers, several per line.

            SAMPLE INPUT (file castle.in)

                7 4
                11 6 11 6 3 10 6
                7 9 6 13 5 15 5
                1 10 12 7 13 7 5
                13 11 10 8 10 12 13
                

            OUTPUT FORMAT

            The output contains several lines:
            Line 1: The number of rooms the castle has.
            Line 2: The size of the largest room
            Line 3: The size of the largest room creatable by removing one wall
            Line 4: The single wall to remove to make the largest room possible

            Choose the optimal wall to remove from the set of optimal walls by choosing the wall farthest to the west (and then, if still tied, farthest to the south). Name that wall by naming the module that borders it on either the west or south, along with a direction of N or E giving the location of the wall with respect to the module.

            SAMPLE OUTPUT (file castle.out)

            5
                        9
                        16
                        4 1 E
                       

            Analysis

            Algorithm:

            Initially, we need to change the bitnumber into an exact wall map. Later, determine the connection of two rooms nearby. In order to determine the room, just use the traditional Floodfill algorithm. Well,everything cames quite easy.

            Code:
                        
            /*
            ID:braytay1
            PROG:castle
            LANG:C++
            */

            #include 
            <fstream>

            using namespace std;

            bool wall[50][50][4];
            int n,m,r_num,size[50*50+1],room[50][50];

            void dfs(int,int);

            int main() {
                ifstream fin (
            "castle.in");
                ofstream fout (
            "castle.out");
                
            int s_max=0,c_max=0,ans_x,ans_y;
                
            char ans_w;
                fin 
            >> n >> m;
                
            for (int i=0;i<m;i++
                    
            for (int j=0;j<n;j++{
                        
            int tem;
                        fin 
            >> tem;
                        
            for (int k=0;k<=3;k++)  wall[i][j][k]=(tem>>k)&1;
                    }

                
            //Initialization
                for (int i=0;i<m;i++
                    
            for (int j=0;j<n;j++
                        
            if (!room[i][j]) {
                            r_num
            ++;
                            size[r_num]
            =0;
                            dfs(i,j);
                            s_max
            =max(s_max,size[r_num]);
                        }

                
            //room mark
                for (int i=0;i<n;i++
                    
            for (int j=m-1;j>=0;j--{
                        
            int a=room[j][i],b=room[j][i<n-1?i+1:0],c=room[j>0?j-1:0][i];
                        
            if (j>0 && wall[j][i][1&& a!=&& size[a]+size[c]>c_max) {
                            c_max
            =size[a]+size[c];
                            ans_x
            =j;
                            ans_y
            =i;
                            ans_w
            ='N';
                        }

                        
            if (i<n-1 && wall[j][i][2&& a!=&& size[a]+size[b]>c_max) {
                            c_max
            =size[a]+size[b];
                            ans_x
            =j;
                            ans_y
            =i;
                            ans_w
            ='E';
                        }

                    }

                
            //break walls
                fout << r_num << endl << s_max << endl << c_max << endl << ans_x+1 << ' ' << ans_y+1 << ' ' << ans_w << endl;
                fin.close();
                fout.close();
                
            return 0;
            }


            void dfs(int x,int y) {
                
            if (room[x][y]==r_num) return;
                room[x][y]
            =r_num;
                size[r_num]
            ++;
                
            if (!wall[x][y][0]) dfs(x,y-1);
                
            if (!wall[x][y][1]) dfs(x-1,y);
                
            if (!wall[x][y][2]) dfs(x,y+1);
                
            if (!wall[x][y][3]) dfs(x+1,y);
            }

            posted on 2008-08-07 14:37 幻浪天空領主 閱讀(409) 評論(0)  編輯 收藏 引用 所屬分類: USACO

            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            導航

            統(tǒng)計

            常用鏈接

            留言簿(1)

            隨筆檔案(2)

            文章分類(23)

            文章檔案(22)

            搜索

            最新評論

            閱讀排行榜

            評論排行榜

            亚洲精品高清国产一线久久| 狠狠色丁香久久婷婷综合五月| 亚洲精品无码久久久久sm| 色诱久久av| 久久久久无码精品国产不卡| 99久久精品无码一区二区毛片| 久久精品亚洲福利| 久久九九兔免费精品6| 亚洲日本va中文字幕久久| 四虎国产精品免费久久久| 久久综合九色综合网站| 久久精品视频网| 无码伊人66久久大杳蕉网站谷歌 | 中文字幕无码av激情不卡久久| 国产成人久久精品一区二区三区 | 久久精品欧美日韩精品| 99久久无码一区人妻| 麻豆一区二区99久久久久| 看全色黄大色大片免费久久久| 国产99久久久国产精免费| 久久青青草原亚洲av无码app| 国产精品熟女福利久久AV| 一本色道久久99一综合| 思思久久99热免费精品6| 一本一道久久精品综合| 九九久久自然熟的香蕉图片| 人人妻久久人人澡人人爽人人精品 | 久久久无码精品亚洲日韩软件| 99国产欧美精品久久久蜜芽 | 亚洲va久久久噜噜噜久久狠狠 | 亚洲中文字幕无码久久精品1| 国产精品女同一区二区久久| 久久久国产精品福利免费| 国产亚洲欧美精品久久久| 精品久久久噜噜噜久久久| 亚洲国产一成人久久精品| 久久人妻无码中文字幕| 久久伊人五月丁香狠狠色| 人妻系列无码专区久久五月天| 久久久久无码国产精品不卡| 久久九九免费高清视频|