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

            PKU1568 Find the Winning Move

            Posted on 2007-03-02 17:50 oyjpart 閱讀(1614) 評論(2)  編輯 收藏 引用 所屬分類: ACM/ICPC或其他比賽

            Find the Winning Move
            Time Limit:3000MS  Memory Limit:32768K
            Total Submit:120 Accepted:67

            Description
            4x4 tic-tac-toe is played on a board with four rows (numbered 0 to 3 from top to bottom) and four columns (numbered 0 to 3 from left to right). There are two players, x and o, who move alternately with x always going first. The game is won by the first player to get four of his or her pieces on the same row, column, or diagonal. If the board is full and neither player has won then the game is a draw.
            Assuming that it is x's turn to move, x is said to have a forced win if x can make a move such that no matter what moves o makes for the rest of the game, x can win. This does not necessarily mean that x will win on the very next move, although that is a possibility. It means that x has a winning strategy that will guarantee an eventual victory regardless of what o does.

            Your job is to write a program that, given a partially-completed game with x to move next, will determine whether x has a forced win. You can assume that each player has made at least two moves, that the game has not already been won by either player, and that the board is not full.

            Input
            The input contains one or more test cases, followed by a line beginning with a dollar sign that signals the end of the file. Each test case begins with a line containing a question mark and is followed by four lines representing the board; formatting is exactly as shown in the example. The characters used in a board description are the period (representing an empty space), lowercase x, and lowercase o. For each test case, output a line containing the (row, column) position of the first forced win for x, or '#####' if there is no forced win. Format the output exactly as shown in the example.

            Output
            For this problem, the first forced win is determined by board position, not the number of moves required for victory. Search for a forced win by examining positions (0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), ..., (3, 2), (3, 3), in that order, and output the first forced win you find. In the second test case below, note that x could win immediately by playing at (0, 3) or (2, 0), but playing at (0, 1) will still ensure victory (although it unnecessarily delays it), and position (0, 1) comes first.

            Sample Input

            ?
            ....
            .xo.
            .ox.
            ....
            ?
            o...
            .ox.
            .xxx
            xooo
            $

             

             

             

            Sample Output

            #####
            (0,1)
            

             

             

             

            Source
            Mid-Central USA 1999

            這個博弈 我用了Alpha-Beta剪枝 搜索是標準的極大極小的搜索過程
            hash用的是4進制的便于位運算的hash

             

            Feedback

            # re: PKU1568 Find the Winning Move   回復  更多評論   

            2007-03-11 19:08 by nick
            const int MAX = (1<<24)+1;

            MAX 不是應該是 (1<<28)

            因為扣掉一開始盤面上一定有兩個子以上 4*4-2 = 14
            然後 2*14 = 28

            為什麼是 1<<24 呢?

            # re: PKU1568 Find the Winning Move   回復  更多評論   

            2007-03-11 19:40 by oyjpart
            [quote] "You can assume that each player has made at least two moves, ..."
            which means that there must be 4 moves at the beginning :)
            99精品国产在热久久无毒不卡| 国产麻豆精品久久一二三| 99久久精品国产综合一区| 99国内精品久久久久久久 | 麻豆av久久av盛宴av| 久久精品黄AA片一区二区三区| 国产亚洲精品美女久久久| 老司机午夜网站国内精品久久久久久久久 | 久久青青国产| 久久久久无码精品国产不卡| 久久久久综合国产欧美一区二区 | 亚洲?V乱码久久精品蜜桃| 亚洲国产精品一区二区久久hs| 99久久久精品免费观看国产| 久久综合五月丁香久久激情| 久久久久AV综合网成人 | 国产精品青草久久久久福利99| 一本久久综合亚洲鲁鲁五月天| 国产精品久久久亚洲| 久久久久久久精品妇女99| 精品欧美一区二区三区久久久| 亚洲综合熟女久久久30p| 久久久久女教师免费一区| 好久久免费视频高清| 无码超乳爆乳中文字幕久久| 麻豆久久久9性大片| 久久er国产精品免费观看8| 99久久超碰中文字幕伊人| 久久久久亚洲AV无码观看| 久久久亚洲精品蜜桃臀| 中文字幕亚洲综合久久| 国内精品久久久久伊人av| 久久精品成人欧美大片| 欧美日韩精品久久久久| 久久综合偷偷噜噜噜色| 久久毛片一区二区| 亚洲国产成人久久一区久久| 亚洲七七久久精品中文国产| 久久亚洲国产成人影院| 狠狠色综合网站久久久久久久高清 | 综合久久给合久久狠狠狠97色 |