Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Crossword Puzzle II

By zobayer · Limits 1s, 512 MB

A crossword puzzle consists of an MxN grid with M rows and N columns. Initially, some of the squares are filled, and some of the squares are empty, which are to be filled by answering the questions. The answers to the questions are written in the empty squares until we reach the puzzle boundaries or initially filled squares.

Filled squares can contain answers for at most two questions, one horizontally, and one vertically. An initially filled square contains a horizontal question if a square to the right exists and is empty. Similarly, an initially filled square contains a vertical question if a square beneath it exists and is empty.

Since you are an expert crossword puzzle solver, you already know all the answers. Now you want to know what could be the minimum number of questions that you needed to answer to solve a given puzzle.

Input

The first line in the input will start with an integer T, (1 <= T <= 30) the number of test cases.

The first line for each test contains two integers, M and N, (2 <= M <= 512, 2 <= N, <= 12) where M and N are the numbers of rows and columns respectively. Each of the next M lines contains N characters, either ‘0’ or ‘1’, denoting an initially empty and an initially filled square respectively. It is guaranteed that all squares from the first row and first column will be filled with ‘1’ and there will be at least one square filled with ‘0’.

Output

For each test case, just output one line containing the minimum number of questions that needed to be answered.

Sample

InputOutput
3
4 5
11111
10000
10000
10000
6 4
1111
1011
1000
1011
1010
1000
9 8
11111111
10000000
10001000
10010001
11100001
10100110
10001000
10100001
10010001
3
4
14

    Discussion

    Statistics


    100% Solution Ratio

    Deshi_TouristEarliest, 4w ago

    Deshi_TouristFastest, 0.1s

    Deshi_TouristLightest, 836 kB

    Deshi_TouristShortest, 3959B

    Submit

    Login to submit

    Toph uses cookies. By continuing you agree to our Cookie Policy.