• <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 閱讀(1613) 評論(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久久久久久97| 人妻无码αv中文字幕久久| 亚洲精品蜜桃久久久久久| 久久久久亚洲AV无码专区首JN| 久久成人小视频| 77777亚洲午夜久久多喷| 日本三级久久网| 欧美无乱码久久久免费午夜一区二区三区中文字幕 | 中文字幕久久精品无码| 久久久午夜精品福利内容| 无码AV波多野结衣久久| 久久精品国产精品亚洲下载| 狠狠色噜噜色狠狠狠综合久久| 国产一区二区精品久久| 日韩va亚洲va欧美va久久| 亚洲国产欧美国产综合久久| 伊人久久综合热线大杳蕉下载| 久久精品国产色蜜蜜麻豆| 国产精品久久久久…| 伊人久久五月天| 精品免费久久久久国产一区| 少妇久久久久久被弄高潮| 久久久久国产成人精品亚洲午夜| 婷婷久久久亚洲欧洲日产国码AV| 精品久久久久久无码国产| 粉嫩小泬无遮挡久久久久久| 亚洲一级Av无码毛片久久精品| 久久精品国产影库免费看| 亚洲国产欧美国产综合久久 | 无夜精品久久久久久| 久久免费小视频| 国产一区二区三区久久| 亚洲愉拍99热成人精品热久久 | 久久久一本精品99久久精品66| 久久青青草原精品国产软件| 香蕉久久一区二区不卡无毒影院| 国内精品人妻无码久久久影院 | 久久久久国产一级毛片高清版| 久久偷看各类wc女厕嘘嘘| 久久精品免费一区二区|