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
Auto comment: topic has been updated by satyamcse (previous revision, new revision, compare).
You mentioned board size $$$N \times M$$$ but nothing about piece size. Should we assume it's also given, say $$$A \times B$$$?
I can do the follow-up version in $$$O(N \times M)$$$. Let's first assume that rotations aren't allowed. Use 2d prefix sums to then check if piece placement is good in $$$O(1)$$$. For every possible placement P, if it's good then we need to make such a move that at least one cell from rectangle P gets covered. For example, if piece size is $$$2 \times 3$$$ and this red rectangle P is all empty, one possible move for me is to use green rectangle (if it's empty too):
We can easily show the area where the top-left corner of my move must be in order to block the red rectangle:
Let's get back to solving the problem. For every possible placement P, if it's good then we get such blue rectangle: area where our top-left corner must be. If there is not even a single possible placement, I can't even make a move. Otherwise, we get a lot of such blue rectangles and their intersection is also a rectangle. We check every cell in the blue-rectangle-intersection as candidate for top-left corner of our move: check with 2d prefix sums if our move would be valid (i.e. no covered cells inside). If yes, we make this move.
If rotations are allowed, run your algorithm twice: once consider your move to be $$$A \times B$$$ and once $$$B \times A$$$. In both runs, your opponent is allowed both rotations too, so consider both types as red rectangles P.
Thanks a lot! Really liked the idea of taking the intersection of all the blue rectangles to keep the time complexity under O(N X M)
omg the candidate master is struggling with a google onsite interview question
Being good in Cp not means good in interview and good software dev . but he has the potential