You are given a 2D vector bookshelf, where each element represents a book type numbered from 1 to k. The task is to empty the bookshelf by selecting a book and removing all books of the same type that lie in the same row or column as the selected book. The goal is to determine the minimum number of turns needed to completely clear the bookshelf.
For instance, if you select a book of type 2 located at row 0 and column 3, you would remove all books of type 2 present in row 0 and column 3, including the selected book.
Example 1:
Input: bookshelf = [[1, 1, 1], [1, 2, 2], [1, 2, 1]], k = 2
Output: 3
Explanation:🐈⬛🐈⬛
Example 2:
Input: bookshelf = [[1, 2, 2], [1, 2, 2], [2, 1, 2]], k = 2
Output: 4
Explanation:For each turn, you select a book and remove all books of the same type either in the same row or column. The objective is to minimize the number of turns it takes to completely empty the bookshelf.
1 <= bookshelf.size() <= 1001 <= bookshelf[0].size() <= 1001 <= k <= 100
input:
output: