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

            Ural 1033 Labyrinth

            Accepted
            0.015 217 KB

            1033. Labyrinth

            Time Limit: 1.0 second
            Memory Limit: 16 MB
            Administration of the labyrinth has decided to start a new season with new wallpapers. For this purpose they need a program to calculate the square of the walls inside the labyrinth. This job is just for you!
            The labyrinth is represented by a matrix N×N (3 ≤ N ≤ 33, you see, ‘3’ is a magic digit!). Some matrix cells contain a dot character (‘.’) that denotes an empty square. Other cells contain a diesis character (‘#’) that denotes a square filled by monolith block of stone wall. All squares are of the same size 3×3 meters.
            The walls are constructed around the labyrinth (except for the upper left and lower right corners, which are used as entrances) and on the cells with a diesis character. No other walls are constructed. There always will be a dot character at the upper left and lower right corner cells of the input matrix.
            Problem illustration
            Your task is to calculate the square of visible part of the walls inside the labyrinth. In other words, the square of the walls' surface visible to a visitor of the labyrinth. Note that there's no holes to look or to move through between any two adjacent blocks of the wall. The blocks are considered to be adjacent if they touch each other in any corner. See picture for an example: visible walls inside the labyrinth are drawn with bold lines. The height of all the walls is 3 meters.

            Input

            The first line of the input contains the single number N. The next N lines contain N characters each. Each line describes one row of the labyrinth matrix. In each line only dot and diesis characters will be used and each line will be finished with a new line character. There will be no spaces in the input.

            Output

            Your program should print to the output a single integer — the exact value of the square of the wallpaper needed.

            Sample

            input output
            5
                        .....
                        ...##
                        ..#..
                        ..###
                        .....
                        
            198
                        

            搜索題:注意的要從兩個入口處搜索,防止中間斷開了
            wa了兩次 找不出錯誤,search(i+1,j)寫成search(i+1,j+1);
            #include<iostream>
            #include
            <cstring>
            using namespace std;

            int const maxSize=35;

            class ural1033
            {
            public:
                ural1033(){ size
            =0; memset(f,0,sizeof f); }
                
            void input();
                
            void print();
                
            void search(int i, int j);
                
            int size;
                
            int getn(){return N;}
            private:
                
            char a[maxSize][maxSize];
                
            bool f[maxSize][maxSize];
                
            int N;
            };

            void ural1033::input()
            {
                 cin
            >>N;
                 
            int i,j;
                 
            for(i=1; i<=N; i++)
                    
            for(j=1; j<=N; j++)
                        cin
            >>a[i][j];
                
            for(i=2; i<=N+1; i++)a[0][i]='#';
                
            for(i=2; i<=N+1; i++)a[i][0]='#';
                
            for(i=1; i<=N-1; i++)a[N+1][i]='#';
                
            for(i=1; i<=N-1; i++)a[i][N+1]='#';

            }

            void ural1033:: search(int i, int j)
            {
                
            if(i<1||i>N||j<1||j>N||a[i][j]=='#'||f[i][j]==1)return ;
                f[i][j]
            =1;
                
            if(a[i-1][j]=='#')size++;
                   
            else search(i-1,j);
                
            if(a[i][j-1]=='#')size++;
                   
            else search(i,j-1);
                
            if(a[i][j+1]=='#')size++;
                   
            else search(i,j+1);
                
            if(a[i+1][j]=='#')size++;
                   
            else search(i+1,j);
            }

            void ural1033::print()
            {
                 
            for(int i=0; i<=N+1; i++,cout<<endl)
                 
            for(int j=0; j<=N+1; j++)
                 cout
            <<a[i][j]<<' ';
                 cout
            <<endl<<endl;
                 
                 
            for(int i=0; i<=N+1; i++,cout<<endl)
                 
            for(int j=0; j<=N+1; j++)
                 cout
            <<f[i][j]<<' ';
            }

            int main()
            {
                ural1033 ural;
                ural.input();
                
                ural.search(
            1,1);
                ural.search(ural.getn(),ural.getn());
                
                cout
            <<ural.size*9<<endl;
                
                system(
            "pause");
                
            return 0;
            }

            posted on 2010-06-24 23:02 田兵 閱讀(393) 評論(0)  編輯 收藏 引用 所屬分類: URAL

            <2010年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導(dǎo)航

            統(tǒng)計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久精品国产第一区二区| 久久精品国产第一区二区三区 | 久久综合久久美利坚合众国| 超级碰碰碰碰97久久久久| 久久国产精品99精品国产| 亚洲精品高清久久| 久久人做人爽一区二区三区| 成人久久久观看免费毛片| 国产午夜福利精品久久| 亚洲精品乱码久久久久久按摩 | 免费一级做a爰片久久毛片潮| 国产精品久久久香蕉| 一本大道久久a久久精品综合| 久久久无码精品亚洲日韩蜜臀浪潮 | 久久精品麻豆日日躁夜夜躁| 久久久99精品一区二区| 精品久久久噜噜噜久久久| 日批日出水久久亚洲精品tv| 99久久国产综合精品麻豆| 97精品依人久久久大香线蕉97 | 国产精品九九久久免费视频| 亚洲香蕉网久久综合影视| 色悠久久久久久久综合网| 99久久精品午夜一区二区| 亚洲va久久久噜噜噜久久天堂| 亚洲国产天堂久久久久久| 香蕉久久夜色精品国产小说| 国产99精品久久| 99久久无色码中文字幕| 国内精品久久久人妻中文字幕| 久久精品国产99国产精品导航 | 国产精品成人精品久久久| 久久99国产精品久久99果冻传媒 | 97久久国产亚洲精品超碰热| 亚洲AV日韩AV天堂久久| 亚洲国产精品嫩草影院久久| 久久人人爽人人澡人人高潮AV| 国产综合精品久久亚洲| 精品欧美一区二区三区久久久 | 久久久久亚洲AV片无码下载蜜桃| 亚洲国产另类久久久精品小说|