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:
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?
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] = '.';
}
}
}
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.
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.
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.
"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!
"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!