Under construction

Still being built. Things may change

Nurikabe

Interview

Time limit1sMemory limit256 MB

Summary
Check whether each numbered island has the required size, all water cells connect, and no 2 by 2 block is all water.
Level

Medium4 of 10

Topics
BFS, Matrix, Implementation
Solved
No attempts yet

Problem

A 9 by 10 Nurikabe grid with numbered cells

Nurikabe is a pencil puzzle from Japan. You are given a rectangular grid. Each cell is either an island cell (white) or a water cell (black), and some island cells carry a number from 1 to 9. A board is filled in correctly when all three rules below hold.

  • Two cells are adjacent when they share a side. Island cells that reach each other along adjacent island cells form one island. Every island contains exactly one numbered cell, and the number of cells in that island equals that number.
  • All water cells are connected into one group under the same adjacency rule.
  • No 2×2 block consists of four water cells. Every 2×2 block of the grid contains at least one island cell.

Decide whether a filled board is correct.

A rule with nothing to apply to holds. A board with no water cell satisfies the second rule, and a board with one row or one column has no 2×2 block.

Input

The first line contains TT, the number of boards.

The first line of each board contains the row count NN and the column count MM, separated by a space. The next NN lines contain the rows of the board, one row per line. Each row is a string of MM characters from 123456789.#, where # is a water cell, a digit is a numbered island cell, and . is an island cell without a number.

  • 0<T≤1000 < T \le 100
  • 1≤N,M≤501 \le N, M \le 50

Output

For each board, print YES on its own line if the board is filled in correctly, and NO otherwise.

Examples4

  1. Example 1

    Input
    2
9 10
2.#...##.2
###..#2###
#2#.7#.#.#
#.######.#
##.#..3#3#
.#2####3##
2##4.#..#.
##..#####.
#1###.2#4.
2 2
#1
1#
    Expected output
    YES
NO

  2. Example 2

    Input
    6
1 1
1
1 1
.
1 1
2
1 1
#
1 3
###
3 1
#
#
#
    Expected output
    YES
NO
NO
YES
YES
YES

  3. Example 3

    Input
    5
2 2
##
##
2 2
1#
##
2 2
4.
..
2 2
1.
..
2 2
12
..
    Expected output
    NO
YES
YES
NO
NO

  4. Example 4

    Input
    4
1 3
12#
1 3
#.#
1 5
2.#.2
1 5
3..#1
    Expected output
    NO
NO
YES
YES