question archive Problem 1: A letter C shape is a set of cells in a square grid that can be painted as follows
Problem 1: A letter C shape is a set of cells in a square grid that can be painted as follows
Subject:Computer SciencePrice: Bought3
Problem 1: A letter C shape is a set of cells in a square grid that can be painted as follows. • Paint a horizontal contiguous segment that consists of at least two cells. Let L and R be the leftmost and the rightmost of these cells. • Starting at L, paint a vertical contiguous segment going downwards. In addition to L this segment must contain at least two more cells. Let the bottom-most of those cells be B. • Starting at B, paint a horizontal contiguous segment going to the right. In addition to B this segment must contain at least one more cell. Below are several valid letter C shapes. The leftmost one is the smallest valid letter C shape
You are given a m × n 2D array grid[.][.], and each cell in grid is either empty (’.’) or blocked (’#’). Cells that are blocked cannot be painted. Design a polynomial time algorithm at counts all the ways in which a letter C shape can be painted into the given grid. Justify the correctness (in 5-6 sentences) and the running time (in 3-4 sentences) of your algorithm. Hint: You need to maintain a two different ’dynamic program tables’, and the also need to fill the tables in different orders.
