Page 1 of 2

### 10111 - Find the Winning Move

Posted: Tue Jun 24, 2003 11:24 am
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,

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?

Posted: Sat Aug 14, 2004 5:21 pm
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.

Posted: Sun Aug 15, 2004 4:36 am
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

### 10111 - Find the Winning Move

Posted: Mon Jun 13, 2005 8:23 pm
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

### looks good..

Posted: Tue Jun 14, 2005 10:52 am
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)
#####
``````

Posted: Tue Jun 14, 2005 11:08 am
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.
``````

### 10111 - Find the Winning Move

Posted: Wed Feb 22, 2006 1:23 pm
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)
#####
#####

Posted: Tue Apr 11, 2006 2:59 am

Input:

Code: Select all

``````?
x...
x...
x...
.ooo
?
o...
.oxx
.xxx
.ooo
\$``````
Output:

Code: Select all

``````(3,0)
(2,0)``````
Hope it helps.

### 10111 - Help with WA, please

Posted: Sun Apr 23, 2006 12:45 pm
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?

### Re: 10111 - Help with WA, please

Posted: Mon Apr 24, 2006 7:42 pm

Code: Select all

``````char board[N][N];
...
char ch;
...
ch=board[0];``````
How can you assign an array into a single character variable?
serur wrote: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.

Posted: Mon Apr 24, 2006 8:59 pm
I think I had it right(both - format and array assigning:))
As I see now I really got nice format! Thank you again!

Posted: Mon Apr 24, 2006 10:13 pm

Code: Select all

``Spoiler removed.``

Posted: Tue Apr 25, 2006 11:25 am
"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!

Posted: Tue Apr 25, 2006 11:25 am
"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!

Posted: Tue Apr 25, 2006 11:58 am
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.