• <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 :)
            久久人人爽人人爽人人片AV不| 一本色道久久HEZYO无码| 日韩精品久久久肉伦网站| 理论片午午伦夜理片久久| 亚洲伊人久久综合影院| 亚洲日本久久久午夜精品| 一本色道久久88综合日韩精品 | 99久久er这里只有精品18| 国内精品久久久久伊人av| 国产精品久久影院| 色综合久久天天综线观看| 18岁日韩内射颜射午夜久久成人 | 青青青青久久精品国产h久久精品五福影院1421 | 热re99久久精品国99热| 日本精品久久久久中文字幕| 久久久久亚洲AV无码专区网站| 久久综合狠狠综合久久综合88| 岛国搬运www久久| 久久精品国产91久久综合麻豆自制 | 久久亚洲精品视频| 99久久久国产精品免费无卡顿| 久久人人超碰精品CAOPOREN| 久久精品国产亚洲av影院| 偷偷做久久久久网站| 中文字幕无码久久精品青草 | 国产99久久久国产精品小说| 国产成人香蕉久久久久| 久久国产成人午夜aⅴ影院| 亚洲国产精品久久久久网站| 94久久国产乱子伦精品免费| 久久久精品免费国产四虎| 97精品伊人久久久大香线蕉| 久久精品国内一区二区三区| 久久精品国产亚洲AV不卡| 久久精品无码一区二区三区免费 | 久久久国产精品福利免费| 国产真实乱对白精彩久久| 欧美亚洲另类久久综合婷婷| 无码人妻精品一区二区三区久久久| 日韩久久久久久中文人妻| 91精品国产91久久久久久青草 |