青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

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 閱讀(1623) 評論(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 :)
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <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>
            欧美国产综合视频| 99精品免费视频| 欧美中文在线观看国产| 亚洲视频在线视频| 国产欧美短视频| 欧美在线综合| 久久久久免费视频| 最新亚洲视频| 日韩一级不卡| 国产精一区二区三区| 久久婷婷久久| 欧美日韩大片| 午夜精品久久| 一区二区欧美日韩视频| 欧美揉bbbbb揉bbbbb| 久久九九有精品国产23| 久久久综合网站| 亚洲精品护士| 欧美一激情一区二区三区| 亚洲激情偷拍| 亚洲综合视频一区| 亚洲电影自拍| 亚洲国产日日夜夜| 欧美母乳在线| 欧美一区二区在线观看| 久久尤物视频| 亚洲欧美日韩系列| 男女精品视频| 久久久久国产精品厨房| 欧美人与禽猛交乱配| 久久伊人精品天天| 欧美亚韩一区| 亚洲第一综合天堂另类专| 国产精品青草综合久久久久99| 欧美不卡一区| 国产色综合网| 欧美福利电影在线观看| 国产精品永久免费| 99精品国产在热久久| 亚洲激情一区二区| 久久电影一区| 久久av在线| 国产精品www色诱视频| 亚洲国产精品综合| 亚洲第一精品夜夜躁人人躁| 亚洲一区二区网站| 亚洲一区成人| 欧美日本亚洲| 亚洲国产另类久久精品| 在线 亚洲欧美在线综合一区| 亚洲免费视频网站| 亚洲一区精品在线| 欧美日韩一区二区欧美激情| 亚洲国产成人久久| 在线观看91精品国产麻豆| 欧美亚洲一区二区三区| 欧美一区二区三区视频在线观看| 欧美色大人视频| 亚洲精品偷拍| 中文日韩在线| 欧美丝袜一区二区三区| 亚洲精品乱码| 中文精品视频| 欧美性一二三区| 亚洲一区二区精品在线观看| 亚洲一区二区四区| 国产精品国产三级国产专区53| 亚洲精品一线二线三线无人区| 99日韩精品| 欧美日韩亚洲一区二| 99成人免费视频| 亚洲一区黄色| 国产一级揄自揄精品视频| 久久久久欧美| 亚洲肉体裸体xxxx137| 亚洲视频欧美在线| 国产精品国产三级国产aⅴ入口| 亚洲一区成人| 老司机午夜精品| 91久久夜色精品国产九色| 欧美精品日韩综合在线| 亚洲午夜av| 久久久蜜臀国产一区二区| 伊人婷婷欧美激情| 欧美精品久久久久久久免费观看 | 激情欧美国产欧美| 久久婷婷丁香| 亚洲精品国精品久久99热| 亚洲午夜91| 狠狠色综合播放一区二区| 欧美成年人在线观看| 一区二区福利| 猛干欧美女孩| 亚洲婷婷免费| 国内精品亚洲| 欧美日韩国产综合视频在线| 亚洲欧美伊人| 亚洲福利视频一区| 欧美一区二区三区四区在线 | 欧美精品激情| 欧美中文字幕在线观看| 亚洲国产专区校园欧美| 久久福利资源站| 亚洲精品在线免费| 国产精品美女在线| 欧美电影免费观看高清完整版| 一本一本a久久| 久久网站热最新地址| 午夜在线精品偷拍| 亚洲另类春色国产| 影音先锋亚洲一区| 国产精品欧美激情| 欧美精品91| 久久亚洲春色中文字幕| 亚洲欧美日韩国产成人| 亚洲欧洲一区二区在线观看| 久久一综合视频| 久久激情视频久久| 亚洲午夜精品在线| 亚洲欧洲偷拍精品| 狠狠久久亚洲欧美| 国产日本欧洲亚洲| 国产精品国产三级国产专播精品人 | 亚洲电影免费观看高清完整版在线| 国产精品成人一区二区网站软件 | 亚洲国产成人在线| 韩国亚洲精品| 国产日韩欧美高清免费| 国产精品毛片高清在线完整版| 久久久亚洲综合| 久久精品夜色噜噜亚洲aⅴ| 亚洲影视在线播放| 亚洲图片在线观看| 亚洲另类在线视频| 久久精品视频在线看| 亚洲一区二区三区久久| 一区二区三区精品国产| 一区二区三区www| aa日韩免费精品视频一| 日韩小视频在线观看专区| 亚洲日韩欧美视频一区| 欧美激情视频免费观看| 欧美精品一区二区三| 欧美极品一区| 欧美区一区二| 国产精品成人一区二区| 国产精品超碰97尤物18| 国产精品毛片a∨一区二区三区|国| 欧美日韩小视频| 国产精品视频免费| 国产日韩综合一区二区性色av| 国产午夜精品理论片a级大结局| 国产美女精品视频| 国产综合久久久久影院| 在线播放日韩| 日韩视频免费观看| 亚洲一二三区在线观看| 亚洲免费在线播放| 久久精品综合一区| 欧美成ee人免费视频| 亚洲激情欧美激情| 亚洲图片在线| 久久久久国产免费免费| 欧美激情一区二区三区不卡| 欧美日韩免费看| 国产午夜精品一区二区三区视频| 国产一区日韩一区| 亚洲精品国产精品国自产观看浪潮| 99精品视频免费在线观看| 欧美综合激情网| 欧美激情一区二区三区在线视频观看| 亚洲精品久久久久久下一站| 一区二区三区蜜桃网| 欧美制服丝袜| 欧美少妇一区| 好看的亚洲午夜视频在线| 亚洲精品一区二区三| 欧美一区二区三区四区视频 | 久久久国产一区二区| 亚洲电影毛片| 欧美一区二区三区日韩视频| 久久蜜桃精品| 欧美性开放视频| 在线日韩日本国产亚洲| 亚洲欧美日韩一区二区在线 | 性做久久久久久久免费看| 欧美国产视频一区二区| 亚洲一区二区三区视频| 欧美电影免费网站| 国产日韩一区欧美| 中国成人在线视频| 欧美激情亚洲一区| 久久精品盗摄| 国产精品日韩一区二区三区| 99re8这里有精品热视频免费| 久久综合九色| 翔田千里一区二区| 欧美丝袜一区二区三区| 亚洲精品乱码视频| 久久综合影音|