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

            oyjpArt ACM/ICPC算法程序設計空間

            // I am new in programming, welcome to my blog
            I am oyjpart(alpc12, 四城)
            posts - 224, comments - 694, trackbacks - 0, articles - 6

            RookAttack

            Posted on 2007-04-16 20:47 oyjpart 閱讀(972) 評論(0)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            Problem Statement

                 You have been given a rows-by-cols chessboard, with a list of squares cut out. The list of cutouts will be given in a String[] cutouts. Each element of cutouts is a comma-delimited lists of coords. Each coord has the form (quotes for clarity) "r c". If coord "r c" appears in an element of cutouts, it means that the square at row r column c (0-based) has been removed from the chessboard. This problem will involve placing rooks on a chessboard, so that they cannot attack each other. For a rook to attack a target piece, it must share the same row or column as the target. Your method will return an int that will be the maximum number of rooks that can be placed on the chessboard, such that no pair of rooks can attack each other. Rooks cannot be placed on cut out squares. The cut out squares do not affect where the rooks can attack.

            Constraints

            - rows will be between 1 and 300 inclusive.
            - cols will be between 1 and 300 inclusive.
            - cutouts will contain between 0 and 50 elements inclusive.
            - Each element of cutouts will contain between 3 and 50 characters inclusive.
            - Each element of cutouts will be a comma delimited list of coords. Each coord will be of the form "r c", where
            • r and c are integers, with no extra leading zeros,
            • r is between 0 and rows-1 inclusive,
            • and c is between 0 and cols-1 inclusive.
            - Each element of cutouts will not contain leading or trailing spaces.

            Examples

            1)
                
            2
            2
            {"0 0","0 1","1 1","1 0"}
            Returns: 0
            2)
                
            3
            3
            {"0 0","1 0","1 1","2 0","2 1","2 2"}
            Returns: 2

            看到這個題目有什么想法?
            8皇后問題相信是大家入門搜索或其他算法的經典教材了 如果被砍掉部分格子呢?
            看到row和col分別是300的時候相信想搜索的朋友們心里可能要嘀咕一下了

            如果這樣分析一下:
            由于在放置rook的時候要求這一行還有這一列一定只有這一個元素(注意是rook 不是queen 不要求斜行)
            也就是說一個rook可以唯一的決定一行和一列
            那么。。
            這個rook似乎可以看成是某一行和某一列的一條邊
            如果把rows作為一個集合 cols作為一個集合 把不是cut out的點作為row和col的連接
            于是就轉化成了:二分圖匹配
            按照最短路的增廣分析 時間復雜度不會超過o(n^3) 滿足題目要求
            比如一個3*3的棋盤 被cut out掉了(0,0) (1,2) (2,2) 3個格子
            row集合 0,1,2
            col集合 0,1,2
            可連接的邊為(0, 1), (0,2), (1, 0), (1,1), (2,0),(2,1)
            執行最大匹配 將會得到如下結果
            (0,2) (1,0), (2,1)
            滿足題意

            欧美激情精品久久久久久久| 狠狠干狠狠久久| 久久亚洲私人国产精品vA| 国产亚洲精品美女久久久| 久久久久女教师免费一区| 亚洲精品无码久久久久去q | 亚洲av日韩精品久久久久久a | 亚洲色欲久久久综合网| 精品久久一区二区| 久久精品aⅴ无码中文字字幕不卡 久久精品成人欧美大片 | 精品伊人久久久| 91久久九九无码成人网站| 久久精品国产亚洲AV影院| 久久人人爽人人爽AV片| 国产婷婷成人久久Av免费高清| 超级碰碰碰碰97久久久久| 久久精品亚洲福利| 色综合久久精品中文字幕首页| 亚洲精品白浆高清久久久久久| 久久综合久久鬼色| 国产巨作麻豆欧美亚洲综合久久 | 国产精品久久久久一区二区三区| 无码久久精品国产亚洲Av影片| 亚洲精品乱码久久久久久不卡| 色偷偷888欧美精品久久久| 国内精品久久国产大陆| 久久久久久毛片免费播放| 色狠狠久久AV五月综合| 久久久久久久波多野结衣高潮| 中文成人久久久久影院免费观看| 久久er国产精品免费观看8| 精品久久人人做人人爽综合| 久久青草国产精品一区| 爱做久久久久久| 精品国产乱码久久久久久浪潮| 青青草国产精品久久| 精品久久久久久国产三级| 欧美午夜精品久久久久久浪潮| 天堂无码久久综合东京热| 四虎国产精品成人免费久久| 亚洲精品无码久久一线|