• <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 1008 Image encoding


            1008. Image encoding

            Time Limit: 2.0 second
            Memory Limit: 16 MB
            Problem illustration
            There are several ways to encode an image. In this problem we will consider two representations of an image. We assume that the image consists of black and white pixels. There is at least one black pixel and all black pixels are connected with their sides. Coordinates of black pixels are not less than 1 and not greater than 10. An example of such an image is at the figure.
            Both representations describe arrangement of black pixels only.
            At the first representation we specify in the first line number of black pixels and coordinates of each black pixel in the following lines. Pixels are listed in order of increasing X. In case of equality of X they are listed in order of increasing Y. Image at the figure is encoded as follows:
            6
            2 3
            2 4
            3 3
            3 4
            4 2
            4 3
            At the second representation we specify in the first line coordinates of the lowest left black pixel. Each of the following lines contains a description of neighbors for one of the pixels. At first, neighbors of the lowest left pixel are specified, then neighbors of its first neighbor (if it exists) are specified, then neighbors of its second neighbor (if it also exists) follow. When all its neighbors are described the description of the neighbors of its first neighbor follows. The description of the neighbors of its second neighbor follows then and so on.
            Each descriptive line contains at most one letter for each neighbor: R for the right, T for the top, L for the left, B for the bottom. If the neighbor was already specified it is not included into the descriptive line and vice-versa. Also there is only one descriptive line for each pixel. Neighbors are listed counter-clockwise starting with the right. Each descriptive line except the last ends with a comma. The last line ends with a full stop. Image at the figure is encoded as follows:
            2 3
            RT,
            RT,
            ,
            B,
            ,
            .
            There are no leading or tailing spaces in any representation. There is exactly one space between X and Y coordinates.

            Input

            One representation of the image will be given to your program in the input.

            Output

            Your program has to write other representation of the image to the output.

            Sample

            input output
            6
                        2 3
                        2 4
                        3 3
                        3 4
                        4 2
                        4 3
                        
            2 3
                        RT,
                        RT,
                        ,
                        B,
                        ,
                        .
                        
            Problem Source: Third Open USTU Collegiate Programming Contest (PhysTech Cup), March 18, 2000

            這題花了不少時間,題目沒看清,只看示例以為只要從第一種方案轉換成第二種,沒想到還有從第二種轉換成第一種
            BFS:
            Accepted     
            0.015        217 KB

            #include<iostream>
            #include
            <queue>
            #include
            <string.h>
            #include
            <string>
            using  namespace std;

            typedef 
            struct point
            {
            int x,y; } point;

            bool graph[12][12]={0};
            bool f[12][12]={0};
            bool print[12][12]={0};

            int n;
            int lbx=10,lby=10;
                          
            void input()
            {
                 
            int x,y;
                 
            for(int i=1; i<=n; i++)
                     {
                          cin
            >>x>>y; graph[x][y]=1;
                          
            if(x<lbx){ lbx=x; lby=y; }
                          
            else if(x==lbx&&y<lby)
                                lby
            =y;
                     }
            }

            void BFS1()    //數字情況 
            {
                 queue
            <point> q;
                 point temp; temp.x
            =lbx; temp.y=lby;
                 cout
            <<lbx<<' '<<lby<<endl;
                 q.push(temp);
                 
            int x,y; int cnt=0;
                 print[lbx][lby]
            =1;
                 
            while(q.size())
                 {
                          temp
            =q.front(); q.pop();
                          x
            =temp.x; y=temp.y;
                          
            if(f[x][y]==1)continue;
                          f[x][y]
            =1;
                          
            if(graph[x+1][y]==1&&!f[x+1][y])
            {
            if(!print[x+1][y]) cout<<'R'; print[x+1][y]=1; temp.x=x+1;temp.y=y; q.push(temp);}
                          
            if(graph[x][y+1]==1&&!f[x][y+1])
            {
            if(!print[x][y+1]) cout<<'T'; print[x][y+1]=1; temp.x=x;temp.y=y+1; q.push(temp);}
                          
            if(graph[x-1][y]==1&&!f[x-1][y])
            {
            if(!print[x-1][y]) cout<<'L'; print[x-1][y]=1; temp.x=x-1;temp.y=y; q.push(temp);}
                          
            if(graph[x][y-1]==1&&!f[x][y-1])
            {
            if(!print[x][y-1]) cout<<'B'; print[x][y-1]=1; temp.x=x;temp.y=y-1; q.push(temp);}
                          
            ++cnt;
                          
            if(cnt==n) cout<<'.'<<endl;
                           
            else  cout <<','<<endl;
                 }
            }

            void BFS2()  // 從R T L B描述轉換成坐標
            {
                 lbx
            =n; cin>>lby;
                 queue
            <point>q;
                 point temp; temp.x
            =lbx; temp.y=lby;
                 q.push(temp);
                 
            string str; int x,y;
                 graph[lbx][lby]
            =1;
                 
            while(q.size())
                 {
                   
                    temp
            =q.front(); q.pop();
                    x
            =temp.x; y=temp.y;
                    
            if(f[x][y])continue;
                    f[x][y]
            =1;
                    cin
            >>str;
                    
            for(int i=0; i<str.size()-1; i++)
                    {
                            
            if(str[i]=='R')     {graph[x+1][y]=1if(!f[x+1][y]){ temp.x=x+1; temp.y=y; q.push(temp);} }
                            
            else if(str[i]=='T'){graph[x][y+1]=1if(!f[x][y+1]){ temp.x=x; temp.y=y+1; q.push(temp);} }
                            
            else if(str[i]=='L'){graph[x-1][y]=1if(!f[x-1][y]){ temp.x=x-1; temp.y=y; q.push(temp);} }
                            
            else if(str[i]=='B'){graph[x][y-1]=1;if(!f[x][y-1]){ temp.x=x; temp.y=y-1; q.push(temp);} }
                    }
                    
            if(str[str.size()-1]=='.')break;
                 }
                 
            int cnt=0;
                 
            for(int i=1; i<=10; i++)
                 
            for(int j=1; j<=10; j++)
                 
            if(graph[i][j])cnt++;
                 cout
            <<cnt<<endl;
                 
            for(int i=1; i<=10; i++)
                 
            for(int j=1; j<=10; j++)
                 
            if(graph[i][j])cout<<i<<' '<<j<<endl;   
            }

            int main()
            {
                cin
            >>n;
                
            if(getchar()=='\n')
                {
                input(); 
                BFS1();
                }
                
            else BFS2();
                system(
            "pause");
                
            return 0;
            }

            posted on 2010-06-26 22:38 田兵 閱讀(342) 評論(0)  編輯 收藏 引用 所屬分類: URAL

            <2010年6月>
            303112345
            6789101112
            13141516171819
            20212223242526
            27282930123
            45678910

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            热RE99久久精品国产66热| 久久久国产精品网站| 久久99精品久久久久久9蜜桃| 国产精品久久国产精麻豆99网站| 久久久无码精品亚洲日韩蜜臀浪潮 | 久久国产成人亚洲精品影院| 久久综合视频网站| 一本久久a久久精品亚洲| 97久久综合精品久久久综合| 久久人妻少妇嫩草AV无码蜜桃| 亚洲国产精品无码久久久秋霞2| 99国产精品久久| 伊人久久大香线蕉综合热线| 91久久精一区二区三区大全| 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区 | 精品无码久久久久久久动漫| 婷婷国产天堂久久综合五月| 久久久久久亚洲Av无码精品专口| 国产精品久久久久久久久久免费| 久久久久av无码免费网| 国产精品xxxx国产喷水亚洲国产精品无码久久一区| 欧美久久天天综合香蕉伊| 国产精品久久久久aaaa| 中文字幕乱码久久午夜| 亚洲国产一成久久精品国产成人综合 | 国产精品久久久福利| 久久精品国产男包| 久久久久亚洲av毛片大| 久久成人国产精品二三区| 天天爽天天狠久久久综合麻豆 | 国产一区二区久久久| 99久久精品国产一区二区| 91精品国产9l久久久久| 人妻少妇久久中文字幕| 精品久久久久成人码免费动漫| 久久精品国产精品亜洲毛片| 久久天堂电影网| 91麻精品国产91久久久久| 亚洲国产精品久久久久久| 亚洲成人精品久久| 久久人人爽人爽人人爽av|