[UVA][博弈] 10111 - Find the Winning Move
Problem A: Find the Winning Move
| Source file: | win.{c, cpp, java, pas} |
| Input file: | win.in |
| Output file: | win.out |
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.
The input file 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.
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.
Example input:
? .... .xo. .ox. .... ? o... .ox. .xxx xooo $
Example output:
##### (0,1)
題目描述：
在一個 4x4 的盤面上，玩井字遊戲，其中一方有連續四個一條即獲勝。
兩條對角線、四條行、四條列共計 10 種。
保證輸入的盤面一定接下來換 x，問接下來 x 要下在哪邊才會必勝，如果有多組解，
則輸出 x, y 座標最小的那組(即左上角)。
題目解法：
考慮使用狀態壓縮，畢竟 3^16 = 43046721 才不算太大。
可以預處理雙方各 10 種的情況，檢查盤面是否已經結束會比較快。
思路是這麼想的，對於 dfs(unsigned int node, int turn)
node 表示盤面, turn 表示接下來換誰，因此 dfs 回傳 0 輸 1 贏。
然後考慮將這一步要放在一個對方必輸的盤面，也就是會產生新的 node 給對方，
而對方一定會輸，那麼這一步一定必勝。
#include <stdio.h>
#include <string.h>
#include <map>
using namespace std;
map<unsigned int, int> R;
unsigned int ow[10] = {}, xw[10] = {};
int check(unsigned int node) {
int i;
for(i = 0; i < 10; i++)
if((node&xw[i]) == xw[i])
return 1;
for(i = 0; i < 10; i++)
if((node&ow[i]) == ow[i])
return 2;
return 0;
}
int dfs(unsigned int node, int &rx, int &ry, unsigned int turn) {
if(R.find(node) != R.end())
return R[node];
int f = check(node);
if(f)
return 0;//lose
int i, j;
int &ret = R[node];
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
if((node>>((i*4+j)*2))&3)
continue;
f = dfs(node|(turn<<((i*4+j)*2)), rx, ry, 3-turn);
if(f == 0) {//win
rx = i, ry = j;
ret = 1;
return 1;
}
}
}
return 0;
}
int main() {
char end[10], g[10][10];
int i, j, n = 0;
//x->1, o->2
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
xw[n] |= 1UL<<((i*4+j)*2);
ow[n] |= 2UL<<((i*4+j)*2);
}
n++;
for(j = 0; j < 4; j++) {
xw[n] |= 1UL<<((j*4+i)*2);
ow[n] |= 2UL<<((j*4+i)*2);
}
n++;
}
for(i = 0; i < 4; i++) {
xw[n] |= 1UL<<((i*4+i)*2);
ow[n] |= 2UL<<((i*4+i)*2);
}
n++;
for(i = 0; i < 4; i++) {
xw[n] |= 1UL<<((i*4+3-i)*2);
ow[n] |= 2UL<<((i*4+3-i)*2);
}
n++;
while(scanf("%s", end) == 1) {
if(end[0] == '$')
break;
for(i = 0; i < 4; i++)
scanf("%s", g[i]);
unsigned int state = 0;
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
if(g[i][j] == '.')
{}
else if(g[i][j] == 'x')
state |= 1UL<<((i*4+j)*2);
else
state |= 2UL<<((i*4+j)*2);
}
}
int rx = -1, ry = -1;
int f = dfs(state, rx, ry, 1);
if(f == 0)
puts("#####");
else
printf("(%d,%d)\n", rx, ry);
}
return 0;
}