• <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一区| 色综合久久久久网| 久久久久无码专区亚洲av| 一本色道久久综合| 久久99亚洲网美利坚合众国| 久久精品国产一区| 99久久综合国产精品免费| 久久99精品久久久久婷婷| 免费一级欧美大片久久网| 精品无码久久久久久午夜| 久久这里只有精品视频99| 人妻无码αv中文字幕久久琪琪布 人妻无码久久一区二区三区免费 人妻无码中文久久久久专区 | 国产精品久久久99| 久久午夜伦鲁片免费无码| 中文字幕亚洲综合久久| 亚洲中文字幕无码久久2020| 久久国产高清一区二区三区| 狠狠色婷婷久久一区二区三区| 亚洲人成无码网站久久99热国产| 国产成人久久AV免费| 中文字幕日本人妻久久久免费| 久久毛片免费看一区二区三区| 少妇人妻88久久中文字幕| 亚洲国产成人久久综合一区77| 国产精品免费久久久久久久久| 99久久人妻无码精品系列| 99精品国产99久久久久久97| 久久综合成人网| 亚洲精品美女久久久久99小说| 久久精品亚洲欧美日韩久久| 中文字幕久久欲求不满| 国产精品99久久久久久人| 久久久久久毛片免费播放| 久久精品国产亚洲AV不卡| 国产农村妇女毛片精品久久| 岛国搬运www久久| 久久久久综合国产欧美一区二区| 久久精品国产99国产精品| 国产精自产拍久久久久久蜜| 97久久精品人人做人人爽|