PROB04 - Đào vàng remix

English

Ti is playing a game of "digging for gold". Different from the familiar gold mining game that we all know.

In this game, gold is spread all over the map, and Ti's job is to pick up gold all over the map.

But it's not as simple as we think, there are many guards on the map on guard duty.

A guard's range is the row and column that this guard is standing in. In other words, Ti is not allowed to pick up gold if there is a guard in the same row and column.

Because time is limited, Ti does not want to waste time picking up gold, but can switch to another level if the amount of gold collected from this map is too little.

I want to ask you to calculate the number of cells in the map that I can go.

Input

The first line is the number of test cases of the problem (1 <= T <= 100.)

With each test case

  • The first line is 2 numbers R, C (1 <= R, C <= 100) describing the map size.
  • Next is the size matrix R×C. Guards are marked as 1, cells without guards are marked with 0.
  • Output

    The result of each test case is printed on 1 line. With:

    Start with the character "#", followed by the ordinal number of that test case, followed by a space (space), and finally the Result of that test case.

    Example

    Input:
    1
    4 4
    1000
    1000
    0011
    0000
    
    Output:
    #1 7

    Vietnamese

    Tí đang chơi 1 trò chơi "đào vàng". Khác với trò đào vàng quen thuộc mà chúng ta đã biết.

    Ở trò chơi này, vàng được dàn trải trên khắp bản đồ, và việc của Tí chỉ là đi nhặt vàng trên toàn bản đồ đó.

    Nhưng không hề đơn giản như ta nghĩ, trên bản đồ còn có nhiều lính canh làm nhiệm vụ canh gác. 

    Phạm vi canh gác của 1 lính canh là Hàng và Cột mà anh lính này đang đứng. Nói cách khác thì Tí không được nhặt vàng tại những hàng, cột có lính canh.

    Do thời gian không có nhiều, nên Tí không muốn tốn thời gian cho việc nhặt vàng, mà có thể chuyển qua màn chơi khác nếu lượng vàng nhặt được từ

    bản đồ này quá ít.

    Tí muốn nhờ các bạn, hãy tính toán số lượng ô trong bản đồ mà Tí có thể đi được.

    Input

    Dòng đầu tiên là số lượng test case của bài toán (1 <= T <= 100)

    Với mối testcase

    - Dòng đầu tiên là 2 số R, C (1 <= R, C <= 100) mô tả kích thước bản đồ

    - Tiếp đến là ma trận kích thước R*C. Lính canh được đánh dấu là 1, các ô không có lính canh được đánh dâu là 0

    Output

    Kết quả mỗi testcase được in trên 1 dòng. Với:

    Bắt đầu bằng ký tự "#", tiếp theo là số thứ tự của testcase đó, tiếp đến là 1 khoảng trắng (dấu cách), và cuối cùng là Kết quả của testcase đó.

    Example

    Input:
    1
    4 4
    1000
    1000
    0011
    0000 Output: #1 7

    Added by:Đặng Xuân Bảo
    Date:2020-03-01
    Time limit:1s
    Source limit:50000B
    Memory limit:1536MB
    Cluster: Cube (Intel G860)
    Languages:All

    © Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.