what is the best way to solve this problem ? game theory? we have N*M empty grid and we have two players each player in his turn take an empty cell and put "X" in it game end when a player can make line with three "X" (like tik-tak-too game) players play optimally so who is the winier in this game?
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 4 | Proof_by_QED | 146 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
Auto comment: topic has been updated by _Evoiz_ (previous revision, new revision, compare).
Auto comment: topic has been updated by _Evoiz_ (previous revision, new revision, compare).
What are the constraints on n, m? If they are very small, then we can do masking to solve this problem.
let say n and m less than 1000
Do diagonal lines also count?
yes diagonal lines counted
Edited: Sorry, I totally misunderstood problem.
can you explain way ?
Sorry, I totally misunderstood problem.
Since the player wins when 3 X's are together, the below solution assumes that either of m or n is greater than or equal to 3.
Player 1 wins only when both m and n are odd. Else player two will win.
The logic is simple. Suppose that either of m or n is not odd. Hence player 2 can always mimic turn of player 1 and upon getting appropriate chance it can make the winning move.
Where as if both m and n are odd, player 1 will place first X in the center square of grid and then player 1 will mimic each turn of player 2 thus on getting appropriate chance player 1 will make the winning move.
Thus player 1wins if both m and n are odd else player 2 wins
i think it's work , thank you.
Sorry, how can the second player win if we have 4x4 grid and the first player starts the game marking by "X" the field (2,2) (here it doesn't matter whether 0-based or 1-based coordinates are)?
i think if n or m less than or equal to two then their is no winner . or we can say that if player didn't find any empty cell he will be lose and game over . so we can see if n or m less than 3 this is special case, other this if n or m is even player 2 will wine
if n or m is even then i can split the grid to two grid (n*m/2) or (n/2*m) and the second player make move like the first player
We can't split it independently, the halfs will affect each other. In case of 4x4 grid and first step (2,2) the second player can't reply symmetrically, otherwise he looses.
so how we solve it in your opinion?
Assuming the grid is 3x3 (like the original tic-tac-toe), by your solution Player 1 is the winner, whereas when both playing optimally in original tic-tac-toe game (3x3 grid), the results are always end up in draws. It contradicts with your solution (I don't know the solution yet, though).
if the first player put "X" in the center of grid ,what ever player two put his "X" the first will can make a line with three "X" .
I didn't get, why if n is odd and m is even the second player wins. For example, if n = 3 and m = 4 then the first player can put X in cell (2, 2) (we suppose lines are numbered from 1 to 3 and columns from 1 to 4). Then the second player has to put in cell (2, 3), doesn't he? If he does, so the first player will win
that's true so we start again how to solve this problem ?
Can you please provide link to the problem so that we can also learn
i am so sorry , their is no link because i write this problem and i didn't find a solution for it . i didn't see this problem in any other online judge before
Quoting from this article. A 3-in-a-row game is a winning game for Player 1 if and only if N >= 3 and M >= 4 (number of row and column can be swapped). Otherwise, it's a draw game (3x3 or smaller grid).
it's not like tic-tak-too because the two players play with "X"
p1: put "X" in cell (2,2)(center);p2: put"X" in cell (1,1);p1: put"X" in cell(3,3) and p1 win
Ah, I see. I'm sorry I misunderstood your problem thinking that thr X from Player 1 and 2 are different.