• <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()    //數(shù)字情況 
            {
                 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 田兵 閱讀(344) 評論(0)  編輯 收藏 引用 所屬分類: URAL

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

            導航

            統(tǒng)計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            欧美精品福利视频一区二区三区久久久精品 | 久久国语露脸国产精品电影| 国产精品日韩深夜福利久久| 久久激情五月丁香伊人| 亚洲国产成人久久综合一| 99热成人精品热久久669| 久久精品国产一区二区 | 日本精品久久久中文字幕| 国产精品免费久久久久影院| 久久久国产视频| 久久91精品久久91综合| 国产成年无码久久久免费| 久久国产精品成人免费| 一本色道久久88综合日韩精品| 久久精品夜夜夜夜夜久久| 日本亚洲色大成网站WWW久久 | 久久夜色精品国产亚洲| 国产精品中文久久久久久久| 国产91久久精品一区二区| 亚洲中文久久精品无码ww16| 久久精品综合一区二区三区| 69久久夜色精品国产69| 性做久久久久久久久浪潮| 久久国产一片免费观看| 国产精品国色综合久久| 久久91精品国产91久| 日韩电影久久久被窝网| 亚洲国产精品久久66| 精品精品国产自在久久高清| 日韩精品久久久久久久电影蜜臀 | 国产亚州精品女人久久久久久 | 久久综合久久伊人| 国产叼嘿久久精品久久| 青青青伊人色综合久久| 久久99精品国产麻豆宅宅 | 7777精品伊人久久久大香线蕉| 国产亚州精品女人久久久久久| yellow中文字幕久久网| 国产亚洲色婷婷久久99精品91| 色噜噜狠狠先锋影音久久| 伊人久久免费视频|