10111 - Find the Winning Move

[Encelado]

Just a doubt I'd like to dispel: the move that causes an immediate victory is still included in the "forced win" situation?
That's an example of the scenario I'm doubting about:

Code: Select all

x...
x...
x...
.ooo

(3,0) is correct?

Moreover, considering this situation:

Code: Select all

o...
.oxx
.xxx
.ooo

the answer should be (2,0) or (3,0)?

TIA,
Encelado

PS: It's the first time that I see some input & output file name specifications on the problem text. Why these are given when it's not allowed to use file I/O functions? It's correct to use standard I/O, or I'm wrong?

[Subeen]

I got WA with my code. some one please post some tests. or you can help me to find the bug in my program. here it is:
[cpp]#include <stdio.h>

char board[6][6];
char *str = "xo";

int game_over()
{
int i, j;

for(i=0; i<4; i++)
for(j=0; j<4; j++)
if(board[j]=='.') return 0;
return 1;
}

int wins(int player)
{
int i, j, count;
char ch = str[player];

count = 0;
for(i=0, j=0; i<4 && j<4; i++, j++)
if(board[j] == ch)
count++;
if(count==4) return 1;
count = 0;
for(i=0, j=3; i<4 && j>=0; i++, j--)
if(board[j] == ch)
count++;
if(count==4) return 1;
for(i=0; i<4; i++)
{
count = 0;
for(j=0; j<4; j++)
if(board[j] == ch)
count++;
if(count==4) return 1;
}
for(i=0; i<4; i++)
{
count = 0;
for(j=0; j<4; j++)
if(board[j] == ch)
count++;
if(count==4) return 1;
}

return 0;
}

int try_to_win(int player)
{
int i, j;
/* check if board is full and no one wins */
if(game_over())
return 1;
/* now find a position where player wins (if any) */
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
if(board[j]=='.')
{
board[j] = str[player];
if( wins(player) )
return player;
board[j] = '.';
}
}
}

/* now find a position where opponent player wins (if any) */
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
if(board[j]=='.')
{
board[j] = str[!player];
if( wins(!player) )
{
board[i][j] = str[player];
if( !try_to_win(!player))
return !player;
}
board[i][j] = '.';
}
}
}

/* otherwise try to put player in next available position */
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
if(board[i][j]=='.')
{
board[i][j] = str[player];
if( try_to_win(!player) )
return 1;
board[i][j] = '.';
}
}
}

return 0;
}

int main()
{
char in[10];
int i, j, flag, x, o;

while(gets(in) && in[0]!='$')
{
for(i=0; i<4; i++) gets(board[i]);

x = o = 0;
for(i=0; i<4; i++)
for(j=0; j<4; j++)
if(board[i][j]=='x') x++;
else if(board[i][j]=='o') o++;
if(x<=2 && o<=2)
{
puts("#####");
continue;
}

flag = 1;
for(i=0; i<4; i++)
{
for(j=0; j<4; j++)
{
if(board[i][j]=='.')
{
board[i][j] = 'x';
if( !try_to_win(1) )
{
flag = 0;
break;
}
}
}
if(!flag) break;
}
if(flag) puts("#####");
else
printf("(%d,%d)\n", i, j);
}
return 0;
}[/cpp]
thank u.

[abishek]

enceldo:

please ignore those input output file specifications. you must use standard input and ouput only. they may be there becoz the questions where picked up from some other local contest.

bye
abi

[Sanny]

Anyone can check these i/o please. I'm getting WA.

Input:

Code: Select all

?
....
.xx.
.oo.
....
?
xoxo
oxox
xoxo
....
?
xoxo
oxox
xoxo
.x.o
?
xx..
....
...o
...o
?
x...
x...
...o
...o
?
....
.xo.
.ox.
....
?
x.x.
ooo.
xxxo
oox.
?
o...
.ox.
.xxx
xooo
?
oxox
xxoo
xxox
o..o
?
....
.xxx
.ooo
....
$

Output:

Code: Select all

#####
(3,3)
#####
#####
#####
#####
#####
(0,1)
(3,1)
(1,0)

If these are correct, then can anyone post some more i/o ?


Regards
Sanny

[sohel]

My AC program produces the same output for the given input..
try these

Input

Code: Select all

?
x..o
....
....
o..x
?
xx.x
ooo.
....
....
?
.ooo
xxx.
....
....
?
.ooo
xxxo
xox.
....
?
.ooo
xxxo
x...
....
$

Output

Code: Select all

#####
(0,2)
(1,3)
(0,0)
#####

[Sanny]

My outputs are same as yours. Think it is time to post the code...

Code: Select all

Got AC now. Recoded it in a better way.

[kuduk]

I solved some examples and I get WA all the time.

Please, can someone check my output or post more examples?

Thanks

?
o..x
.ox.
....
....
?
.x..
oxxo
oxoo
x...
?
xooo
xxo.
xox.
....
?
oxx.
xoo.
xxo.
....
?
....
xxx.
ooo.
....
?
..x.
.x..
x...
ooo.
?
...o
xoo.
xxx.
xoo.
?
x...
.xo.
.ox.
o...
?
o...
.ox.
.xo.
x...
?
o...
.o..
xxo.
x...
?
xoox
x.ox
....
xoox
?
...x
.xo.
.ox.
..o.
?
x.ox
.x.o
ox.o
xoox
?
ox.o
xo..
xo..
oxxo
?
....
.xo.
.ox.
....
?
o...
.ox.
.xxx
xooo
?
....
.xx.
.oo.
....
?
xoxo
oxox
xoxo
....
?
xoxo
oxox
xoxo
.x.o
?
xx..
....
...o
...o
?
x...
x...
...o
...o
?
....
.xo.
.ox.
....
?
x.x.
ooo.
xxxo
oox.
?
o...
.ox.
.xxx
xooo
?
oxox
xxoo
xxox
o..o
?
....
.xxx
.ooo
....
?
ooo.
xox.
x.o.
xx..
?
xoo.
xxoo
oxoo
xxoo
$


SOLUTIONS:

#####
(0,0)
(3,0)
#####
(1,3)
#####
(0,0)
(3,3)
(0,3)
#####
(2,2)
#####
(0,1)
#####
#####
(0,1)
#####
(3,3)
#####
#####
#####
#####
#####
(0,1)
(3,1)
(1,0)
#####
#####

[Jan]

To Encelado.

Input:

Code: Select all

?
x...
x...
x...
.ooo
?
o...
.oxx
.xxx
.ooo
$

Output:

Code: Select all

(3,0)
(2,0)

Hope it helps.

[serur]

Hello Fellows!

The problem is- 10111. I want you to help me.
The code copes with every testcase posted here, but OJ responds WA... Well, before WA it works a good deal - 6.358 CPU,
but it may be only due to recursion...
This problem is just another perfect strategy problem, isn't it?
It can be placed next to 10578-"The Game of 31", for example...
To Game Theory experts - are there any problems in UVa about minimax search and alpha-beta search?

[Jan]

See your code...

Code: Select all

char board[N][N]; 
...
char ch; 
...
ch=board[0];

How can you assign an array into a single character variable?

Well, I see that my code looks here very awkward - so tell me please how to make the nice formatting that you did here(with green colour and all that)?

Well, in the editor (you use to post), you will find some options in the upper side. Just select any part and click the 'code' button in the editor. That part will be formatted as you wanted.

Hope it helps.

[serur]

[Jan, thank you for reply!
I think I had it right(both - format and array assigning:))
As I see now I really got nice format! Thank you again!

[Jan]

Code: Select all

Spoiler removed.

[serur]

"The game is won by the first player to get four of his or her pieces on the same row, column, or diagonal."

"You can assume that ... the game has not already been won by either player"

Did I understand the problem in the wrong way? If so, your input is valid and my mistake in gemover() function... Or again, the problem statement is wrong!

[serur]

"The game is won by the first player to get four of his or her pieces on the same row, column, or diagonal."

"You can assume that ... the game has not already been won by either player"

Did I understand the problem in the wrong way? If so, your input is valid and my mistake in gemover() function... Or again, the problem statement is wrong!

[Jan]

Try the following I/O set...

Input:

Code: Select all

?
x.o.
.x.o
..xo
.xo.
?
x.o.
.x..
o.xo
.xo.
?
x...
ox.o
..xo
.xo.
$

Output:

Code: Select all

(0,1)
(0,1)
(0,1)

Hope it helps.