Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1477
The Game of Euler is played between two players on a 4×4 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 3 XXX. XXX. .XXX .XXX XXXX ...X XX.X XX.X .... .... .... ....
Sample Output LOSING WINNING LOSING
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int ok = (1<<16)-1;
vector<int> memo(1<<16,-1);
vector < vector<int>> dirs = {{1,0},{0,1},{-1,0},{0,-1}};
bool solve(int bitmask) {
if(bitmask == ok) return true;
if(memo[bitmask] != -1) return memo[bitmask] == 1;
bool solved = false;
for(int i=0;i<4 && !solved;i++){
for(int j=0;j < 4 && !solved;j++){
int idx = i*4+j;
if(bitmask & (1<<idx)) continue;
int next_bitmask = bitmask | (1<<idx);
solved = !solve(next_bitmask);
if(solved) break;
for(auto& dir : dirs>{
bool ok = true;
int x=i,y=j;
int next_bitmask = bitmask;
while(ok && x>=0 && y>=0 && x < 4 && y<4){
idx = x*4+y;
// check if already covered and pin is not larger than size 3
if(bitmask & (1<<idx) || abs(x-i)>2 || abs(y-j)>2) {
ok=false; break;
}
next_bitmask |= (1<<idx);
x += dir[0], y+= dir[1];
}
if(ok) {
solved = !solve(next_bitmask);
if(solved) break;
}
}
}
}
return memo[bitmask] = solved ? 1 : 0;
}
int main() {
int t;
string in;
scanf("%d",&t);
while(t--){
int bits = 0;
for(int i=0;i<4;i++){
cin >> in;
for(int j=0;j < 4;j++)
if(in[j] == 'X') bits |= 1<<(i*4+j);
}
if(solve(bits)) printf("WINNING\n");
else printf("LOSING\n">;
}
}
Input
XXX.
XXX.
.XXX
.XXX
XXXX
...X
XX.X
XX.X
....
....
....
....
Output
WINNING
LOSING
Demonstration
UVA Online Judge solution - 10536-Game of Euler - UVA Online Judge solution in C,C++,java