This question is originally posted on LeetCode by several anonymous users but it doesn't have any good answer there.

You are implementing a board game where you are given a size N x M for the board, where N is the number of rows and M is the number of columns. In this board game, you are playing with some fixed size lego pieces, where each player places 1 piece on the board every turn until no more piece can fit onto the board, and the last player to move wins.

The problem is to implement a method for making a move on this board, placing a piece wherever there is space available and returns a boolean indicating whether or not the player that has just made the move has won.

Follow up question: The method should also find if there is any move that can be made that will make it so that the next player is unable to place a piece anywhere on the board in their next turn, and make that move.

You choose how to represent the board and lego pieces in the problem and lego piece would be rectangular.

Simple example (small board for demonstration purposes, board length = 2 x 3, lego piece length = 1 x 2): Empty Board:

O O O
O O O

Board after player 1 makes move, placing lego piece at the top right corner:

O X X
O O O

At this point, player 2 can make a move that will prevent player 1 from placing another piece:

O X X
X X O

and so the method should be able to find and make that winning move, rather than an alternative move that would miss an opportunity for a win:

O X X
O X X