[UVA] 10536 - Game of Euler
Problem F
Game of Euler
Input: Standard Input
Output: Standard Output
Time Limit: 3 Seconds
The Game of Euler is played between two players on a 4x4 board. The board is initially empty. The players alternatively put pins of different lengths on the board. You can either put them from one of the sides, in which case the pin will cover the same number of squares as the length of the pin (1, 2 or 3), or you can put it perpendicular to the board (pushing it straight down), covering exactly 1 square. A pin may only cover squares that are not covered already. The player who puts the last pin, and thus makes all 16 squares covered, loses. Both players have an infinite supply of pins of length 1, 2 and 3.
Consider the position in the picture to the right. If the player to move covers one of the two squares in either corner, the opponent will cover both squares in the opposite corner, so the first player will have only one move and will thus lose. But if the first player covers both squares in one corner, the opponent will cover only one square in the other corner, winning again. So the first player will lose the game no matter what move he makes. We say that such a position is losing for the player to move, because no matter which move he makes, he will lose the game if the opponent plays "perfectly" (that is, make the best moves). If the position is not losing, it is winning. Since fewer and fewer squares remains uncovered as the play progresses, the game will always end with a loser and a winner (never a draw).
Input
The first line in the input contains an integer N the number of test cases to follow (N < 100,000). Each test case contains of 4 lines, each line containing four character. These lines represent which squares of the board have been covered so far. A covered square is indicated by a 'X', an uncovered square is indicated by a '.'. At least one square on the board will be uncovered. Each test case is preceded by a blank line.
Output
For each test case output a single line containing either "LOSING" or "WINNING" depending on whether the position is losing or winning for the player to move.
Sample Input Output for Sample Input
3 XXX.XXX..XXX.XXX XXXX...XXX.XXX.X ................ |
LOSINGWINNINGLOSING
|
Problemsetter: Jimmy Mårdell, Member of Elite Problemsetters' Panel
題目描述：
這個遊戲只會在 4x4 的盤面上，兩名玩家輪流放置螺絲，螺絲放置有兩種情況，
只能從"邊緣"插入，或者垂直插入。而螺絲長度可選擇 1~3 三種可能。
放下最後一根螺絲的人輸。
給定一個中途的盤面，兩個人都按照最佳化策略進行，問先手是輸還是贏。
題目解法：
每個盤面的狀態可以壓縮成 16 bit，接著進行博弈 dp。
特別要注意只能從邊緣插入，不能放置中間！而垂直插入必然只能造成一格。
#include <stdio.h>
#include <algorithm>
using namespace std;
char g[5][5];
int dp[65536], used[65536] = {};
int dfs(int state) {
if(state == 65535)
return 1;
if(used[state])
return dp[state];
int &ret = dp[state];
int i, j, k, l;
static int dx[] = {0,0,1,-1};
static int dy[] = {1,-1,0,0};
ret = 0;
used[state] = 1;
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
if((state>>(i*4+j))&1)
continue;
ret |= !dfs(state|(1<<(i*4+j)));//perpendicular insert
if(ret)
return ret;
for(k = 0; k < 4; k++) {
int x, y, pin = 0;
x = i, y = j;
if(x-dx[k] >= 0 && x-dx[k] < 4 && y-dy[k] >= 0 && y-dy[k] < 4)
continue;//should outside, insert.
for(l = 0; l < 3; l++) {
pin |= 1<<(x*4+y);
ret |= !dfs(state|pin);
if(ret)
return ret;
x += dx[k], y += dy[k];
if(x < 0 || y < 0 || x >= 4 || y >= 4)
break;
if((state>>(x*4+y))&1)
break;
}
}
}
}
return ret;
}
int main() {
int testcase;
int i, j, k;
scanf("%d", &testcase);
while(testcase--) {
int state = 0;
for(i = 0; i < 4; i++)
scanf("%s", &g[i]);
for(i = 0; i < 4; i++) {
for(j = 0; j < 4; j++) {
if(g[i][j] == 'X')
state |= 1<<(i*4+j);
}
}
int ret = dfs(state);
puts(ret ? "WINNING" : "LOSING");
}
return 0;
}