• <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年8月>
            25262728293031
            1234567
            891011121314
            15161718192021
            22232425262728
            2930311234

            導航

            統計

            常用鏈接

            留言簿(2)

            隨筆分類(65)

            隨筆檔案(65)

            文章檔案(2)

            ACM

            搜索

            積分與排名

            最新隨筆

            最新評論

            閱讀排行榜

            久久久久亚洲AV无码去区首| 伊人久久精品无码av一区| 99久久99这里只有免费费精品| 中文国产成人精品久久不卡| 欧洲人妻丰满av无码久久不卡 | 国内精品九九久久久精品| 国产成人精品久久一区二区三区| 国产高潮国产高潮久久久91 | 一本大道久久a久久精品综合 | 激情五月综合综合久久69| 久久人人爽人人精品视频| 久久久无码人妻精品无码| 久久精品国产欧美日韩| 久久久久久九九99精品| 久久精品国产一区二区三区不卡 | 日韩一区二区久久久久久| 日本精品久久久久影院日本| 午夜不卡久久精品无码免费| 一本一本久久aa综合精品| 久久99热这里只频精品6| 久久99国内精品自在现线| 久久久久无码精品国产app| 乱亲女H秽乱长久久久| 色天使久久综合网天天| 狠狠色丁香久久综合婷婷| 色综合久久夜色精品国产| 久久免费高清视频| 亚洲午夜久久久久妓女影院 | 中文字幕亚洲综合久久菠萝蜜| 久久精品国产亚洲AV大全| 大蕉久久伊人中文字幕| 久久久久夜夜夜精品国产| 久久久久AV综合网成人| 久久亚洲精品中文字幕| 久久久无码精品亚洲日韩蜜臀浪潮| yy6080久久| 久久国产色av免费看| 亚洲精品无码专区久久久| 亚洲中文久久精品无码| 久久夜色精品国产噜噜亚洲AV | 久久久无码精品亚洲日韩京东传媒 |