• <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算法程序設(shè)計(jì)空間

            // 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) 評(píng)論(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

            這個(gè)博弈 我用了Alpha-Beta剪枝 搜索是標(biāo)準(zhǔn)的極大極小的搜索過(guò)程
            hash用的是4進(jìn)制的便于位運(yùn)算的hash

             

            Feedback

            # re: PKU1568 Find the Winning Move   回復(fù)  更多評(píng)論   

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

            MAX 不是應(yīng)該是 (1<<28)

            因?yàn)榭鄣粢婚_(kāi)始盤面上一定有兩個(gè)子以上 4*4-2 = 14
            然後 2*14 = 28

            為什麼是 1<<24 呢?

            # re: PKU1568 Find the Winning Move   回復(fù)  更多評(píng)論   

            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 :)
            亚洲精品午夜国产VA久久成人| 久久国语露脸国产精品电影| 久久久老熟女一区二区三区| 久久久久亚洲AV片无码下载蜜桃 | 久久99热精品| 日韩亚洲国产综合久久久| 久久久黄色大片| 久久精品国产亚洲欧美| 污污内射久久一区二区欧美日韩| 亚洲级αV无码毛片久久精品 | 一本久久综合亚洲鲁鲁五月天亚洲欧美一区二区| 四虎国产精品成人免费久久| 久久精品国产亚洲AV不卡| 99热都是精品久久久久久| 久久久久久久久久久| 久久黄视频| 亚洲一区中文字幕久久| 中文字幕乱码人妻无码久久| 久久精品无码一区二区日韩AV| 久久精品国产亚洲av水果派 | 精品久久久久久无码国产| 伊人久久大香线焦AV综合影院| 久久国产精品偷99| 97久久精品人妻人人搡人人玩| 久久久久波多野结衣高潮| 久久毛片免费看一区二区三区| 国产精品久久永久免费| 亚洲国产精品无码久久| 久久亚洲精品成人无码网站| 久久经典免费视频| 欧美精品丝袜久久久中文字幕 | 精品久久久久久久久久久久久久久| 国内精品九九久久久精品| 久久综合香蕉国产蜜臀AV| 一本色道久久HEZYO无码| 亚洲午夜久久久久妓女影院| 久久久久久精品久久久久| 亚洲精品视频久久久| 久久国产精品成人免费| 久久久久亚洲精品中文字幕 | 亚洲精品美女久久久久99|