• <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 :)
            久久人人爽人人爽人人片av麻烦| 99蜜桃臀久久久欧美精品网站| 国产精品久久国产精品99盘| 久久婷婷久久一区二区三区| 久久男人中文字幕资源站| 亚洲欧美精品一区久久中文字幕 | 久久亚洲私人国产精品vA| 国产精品99久久久久久猫咪| 久久99热这里只有精品66| 久久国产精品无码HDAV| 一本一道久久a久久精品综合| 久久久久亚洲精品无码蜜桃| 久久久久国产亚洲AV麻豆| 国产成人久久精品激情| 久久久久久久久66精品片| 精品人妻伦一二三区久久| 狠狠色丁香久久综合婷婷| 亚洲午夜无码久久久久| 一本大道久久香蕉成人网| 久久精品人妻一区二区三区| 久久国产乱子精品免费女| 国产精品久久久久国产A级| 亚洲国产精品无码久久久秋霞2| 久久久久国产一区二区| 狠狠精品干练久久久无码中文字幕| 国内精品久久久久影院免费| 久久99热只有频精品8| 久久青青草原精品国产| 亚洲va久久久噜噜噜久久男同 | 人妻少妇久久中文字幕一区二区| 久久综合狠狠综合久久97色| 久久九九久精品国产免费直播| 精品久久久久久久| 亚洲欧美精品伊人久久| 久久91精品国产91久久小草| 国产91色综合久久免费| 国内精品伊人久久久久| 国产精品美女久久久网AV| 久久中文精品无码中文字幕| 色综合久久中文字幕综合网| 99久久这里只精品国产免费|