Problem Type : Finding Connected Components (BFS/DFS)
Let us try to understand the problem
"The game ‘Il Gioco dell’ X’ is played on a N by N board (N ≥ 2). The object of both players, say Black and White, is to join opposite sides of the board by placing in turn their pawns on the board in such a way that a path is made from one side to the other by adjacent (neighboring) pawns of their own color."
Though the statement is not very clear how Black and White will win but we can get the idea from the given picture
From the first example we can see that for White to win there has to be a connected components of White pawns form left to right. For Black to win there has to be a connected components of Black pawns form up to down.
"this game cannot end in a draw (that is, without winner)" meaning there has to be a winner. So we can search the board for either black or white pawn connected components, if it doesn't exist then other one is the winner
We can find this connected components with either bfs or dfs :D
Let us try to understand the problem
"The game ‘Il Gioco dell’ X’ is played on a N by N board (N ≥ 2). The object of both players, say Black and White, is to join opposite sides of the board by placing in turn their pawns on the board in such a way that a path is made from one side to the other by adjacent (neighboring) pawns of their own color."
Though the statement is not very clear how Black and White will win but we can get the idea from the given picture
From the first example we can see that for White to win there has to be a connected components of White pawns form left to right. For Black to win there has to be a connected components of Black pawns form up to down.
"this game cannot end in a draw (that is, without winner)" meaning there has to be a winner. So we can search the board for either black or white pawn connected components, if it doesn't exist then other one is the winner
We can find this connected components with either bfs or dfs :D
No comments:
Post a Comment