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

            pku1856 Sea Battle 網格圖的聯通分量

            題意是這樣,一個海面上有N條船,用長方形表示。海域中#代表有船的格子,.代表沒船的格子。統計共有多少條船。
            如果兩條船有接觸的話(包括頂點接觸),則判為不合法。
            說下判斷不合法的情況如何判斷吧。
            DFS或者BFS求聯通分量的時候,維護左上角坐標(r1,c1)和右下角坐標(r2,c2),再統計出聯通分量中的網格數num。如果(r2-r1+1)*(c2-c1+1)!=num,就不合法。
            開始我沒注意不能夠頂角相連,所以在算聯通分量的時候僅僅向(r-1,c) (r+1,c) (r,c-1) (r,c+1)轉移,事實上還要向(r-1,c-1) (r+1,c+1) (r-1,c+1) (r+1,c-1)轉移。細心啊細心,regional被這種題粉掉就要撞墻了
            貼代碼

             1# include <iostream>
             2# include <cstring>
             3# include <cstdio>
             4# include <queue>
             5using namespace std;
             6bool used[1200000];
             7char map[1001][1002];
             8# define encode(a,b) (((a)<<10)|(b))
             9queue<int> q;
            10int main()
            11{
            12    int r,c,i,j;
            13    while(true)
            14    {
            15        scanf("%d%d",&r,&c);
            16        if(!r&&!c) break;
            17        for(i=0;i<r;i++)
            18            scanf("%s",map[i]);
            19        int res=0;
            20        bool flag=true;
            21        memset(used,0,sizeof(used));
            22        for(i=0;i<r&&flag;i++)
            23            for(j=0;j<c&&flag;j++)
            24                if(map[i][j]=='#')
            25                {
            26                    int r1=0xfffffff,c1=0xfffffff,r2=-1,c2=-1,num=0;
            27                    while(!q.empty()) q.pop();
            28                    q.push(encode(i,j));
            29                    used[encode(i,j)]=true;
            30                    while(!q.empty())
            31                    {
            32                        int tr=q.front()>>10,tc=q.front()&1023;
            33                        q.pop();
            34                        num++;
            35                        map[tr][tc]='.';
            36                        if(tr<r1||tr==r1&&tc<c1) r1=tr,c1=tc;
            37                        if(tr>r2||tr==r2&&tc>c2) r2=tr,c2=tc;
            38                        if(tr+1<r&&map[tr+1][tc]=='#'&&!used[encode(tr+1,tc)])
            39                        {
            40                            q.push(encode(tr+1,tc));
            41                            used[encode(tr+1,tc)]=true;
            42                        }

            43                        if(tr-1>=0&&map[tr-1][tc]=='#'&&!used[encode(tr-1,tc)])
            44                        {
            45                            q.push(encode(tr-1,tc));
            46                            used[encode(tr-1,tc)]=true;
            47                        }

            48                        if(tc+1<c&&map[tr][tc+1]=='#'&&!used[encode(tr,tc+1)])
            49                        {
            50                            q.push(encode(tr,tc+1));
            51                            used[encode(tr,tc+1)]=true;
            52                        }

            53                        if(tc-1>=0&&map[tr][tc-1]=='#'&&!used[encode(tr,tc-1)])
            54                        {
            55                            q.push(encode(tr,tc-1));
            56                            used[encode(tr,tc-1)]=true;
            57                        }

            58                        if(tc-1>=0&&tr-1>=0&&map[tr-1][tc-1]=='#'&&!used[encode(tr-1,tc-1)])
            59                        {
            60                            q.push(encode(tr-1,tc-1));
            61                            used[encode(tr-1,tc-1)]=true;
            62                        }

            63                        if(tc-1>=0&&tr+1<r&&map[tr+1][tc-1]=='#'&&!used[encode(tr+1,tc-1)])
            64                        {
            65                            q.push(encode(tr+1,tc-1));
            66                            used[encode(tr+1,tc-1)]=true;
            67                        }

            68                        if(tc+1<c&&tr-1>=0&&map[tr-1][tc+1]=='#'&&!used[encode(tr-1,tc+1)])
            69                        {
            70                            q.push(encode(tr-1,tc+1));
            71                            used[encode(tr-1,tc+1)]=true;
            72                        }

            73                        if(tc+1<c&&tr+1<r&&map[tr+1][tc+1]=='#'&&!used[encode(tr+1,tc+1)])
            74                        {
            75                            q.push(encode(tr+1,tc+1));
            76                            used[encode(tr+1,tc+1)]=true;
            77                        }

            78                    }

            79                    if((r2-r1+1)*(c2-c1+1)!=num) flag=false;
            80                    else res++;
            81                }

            82        if(flag) printf("There are %d ships.\n",res);
            83        else printf("Bad placement.\n");
            84    }

            85    return 0;
            86}

            87
            88

            posted on 2010-11-01 19:36 yzhw 閱讀(220) 評論(0)  編輯 收藏 引用 所屬分類: searchdata struct

            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            導航

            統計

            公告

            統計系統

            留言簿(1)

            隨筆分類(227)

            文章分類(2)

            OJ

            最新隨筆

            搜索

            積分與排名

            最新評論

            閱讀排行榜

            中文精品久久久久国产网址| 久久精品国产亚洲av麻豆小说 | 久久久av波多野一区二区| 伊人 久久 精品| 欧美日韩精品久久免费| 看久久久久久a级毛片| 色综合久久久久网| 久久国产亚洲精品| 国产精品一久久香蕉国产线看观看| 精品一区二区久久| 国产成人精品久久| 久久精品国产色蜜蜜麻豆| 要久久爱在线免费观看| 久久久久人妻一区二区三区vr| 国产AV影片久久久久久 | 亚洲欧美国产精品专区久久| 亚洲AV日韩精品久久久久久久| 久久WWW免费人成—看片| 久久99国产精品久久99| 亚洲国产视频久久| 99热热久久这里只有精品68| 久久久久亚洲av无码专区| 人妻无码精品久久亚瑟影视| 国产亚州精品女人久久久久久| 一本久久a久久精品vr综合| 久久国产综合精品五月天| 国产精品久久久久久久久| 日韩人妻无码精品久久免费一| 久久人人爽人爽人人爽av | 久久亚洲高清观看| 人妻少妇久久中文字幕一区二区| 亚洲国产成人精品91久久久| 久久国产精品免费一区| 91久久精品视频| 久久国产精品-国产精品| 国产精品毛片久久久久久久| 久久精品人成免费| 精品久久久久久成人AV| 久久精品黄AA片一区二区三区| 亚洲AV无码成人网站久久精品大| 久久WWW免费人成一看片|