Karat 003 Nonogram

A nonogram is a logic puzzle, similar to a crossword, in which the player is given
a blank grid and has to color it according to some instructions. Specifically,
each cell can be either black or white, which we will represent as 0 for black and
1 for white.
+————+
| 1 1 1 1 |
| 0 1 1 1 |
| 0 1 0 0 |
| 1 1 0 1 |
| 0 0 1 1 |
+————+
For each row and column, the instructions give the lengths of contiguous runs of
black (0) cells. For example, the instructions for one row of [ 2, 1 ] indicate
that there must be a run of two black cells, followed later by another run of one
black cell, and the rest of the row filled with white cells.
These are valid solutions: [ 1, 0, 0, 1, 0 ] and [ 0, 0, 1, 1, 0 ] and also [ 0,
0, 1, 0, 1 ]
This is not valid: [ 1, 0, 1, 0, 0 ] since the runs are not in the correct order.
This is not valid: [ 1, 0, 0, 0, 1 ] since the two runs of 0s are not separated by
1s.
Your job is to write a function to validate a possible solution against a set of
instructions. Given a 2D matrix representing a player’s solution; and instructions
for each row along with additional instructions for each column; return True or
False according to whether both sets of instructions match.

题目大意：

Nonogram日本游戏，0表示黑子，[2, 1]表示黑子的连续数目，如棋盘状态[ 1, 0, 0, 1, 0 ]，表示连续黑子数为[2, 1]
[ 1, 0, 0, 0, 1 ]连续黑子数为[3]. 验证棋盘的每一行和每一列是否满足rows和cols所指定的连续黑子数

解题思路：

按题意求解

解题步骤：

N/A

注意事项：

1. 递归只有一种情况
2. 答案需求全局

Python代码：

def valid_nonogram(self, matrix, rows, cols):
	for i in range(len(matrix)):
		if self.get_consecutive_zeros(matrix[i]) != rows[i]:
			return False
	for j in range(len(matrix[0])):
		col_vals = []
		for i in range(len(matrix)):
			col_vals.append(matrix[i][j])
		if self.get_consecutive_zeros(col_vals) != cols[j]:
			return False
	return True

# [ 1, 0, 0, 1, 0 ] -> [2, 1], # of 0s
def get_consecutive_zeros(self, matrix_row):
	count, res = 0, []
	for n in matrix_row:
		if n == 0:
			count += 1
		else:
			if count > 0:
				res.append(count)
			count = 0
	if count > 0:
		res.append(count)
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(n)