10111 - Find the Winning Move

All about problems in Volume 101. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Encelado
New poster
Posts: 3
Joined: Mon May 26, 2003 4:55 pm
Location: Italy

10111 - Find the Winning Move

Post by Encelado » 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,
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
Experienced poster
Posts: 127
Joined: Tue Nov 06, 2001 2:00 am
Location: Bangladesh
Contact:

Post by Subeen » 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.

User avatar
abishek
Experienced poster
Posts: 131
Joined: Mon Dec 15, 2003 5:41 am

Post by abishek » 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

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

10111 - Find the Winning Move

Post by Sanny » 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

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

looks good..

Post by sohel » 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)
#####

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » 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.

kuduk
New poster
Posts: 1
Joined: Wed Feb 22, 2006 1:18 pm

10111 - Find the Winning Move

Post by kuduk » 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)
#####
#####

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Apr 11, 2006 2:59 am

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.
Ami ekhono shopno dekhi...
HomePage

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

10111 - Help with WA, please

Post by serur » 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?
Last edited by serur on Sat Apr 14, 2012 3:34 pm, edited 2 times in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 10111 - Help with WA, please

Post by Jan » Mon Apr 24, 2006 7:42 pm

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?
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.
Ami ekhono shopno dekhi...
HomePage

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Mon Apr 24, 2006 8:59 pm

[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!
Last edited by serur on Tue Apr 25, 2006 4:19 pm, edited 1 time in total.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Apr 24, 2006 10:13 pm

Code: Select all

Spoiler removed.
Last edited by Jan on Tue Apr 25, 2006 3:27 pm, edited 2 times in total.
Ami ekhono shopno dekhi...
HomePage

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » 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!

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » 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!

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » 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.
Last edited by Jan on Tue Apr 25, 2006 3:21 pm, edited 1 time in total.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 101 (10100-10199)”