trang chủ / đề bài / icpc22_nat_j

Nhà của đàn khỉ

Đề bài

Mô tả

Đàn khỉ vừa chuyển đến một khu rừng hình chữ nhật, có thể mô hình hóa thành một bảng gồm n hàng và m cột. Các hàng được đánh số từ 1 đến n theo hướng từ Bắc xuống Nam, các cột được đánh số từ 1 đến m theo hướng từ Tây sang Đông. Ô ở hàng thứ r và cột thứ c được ký hiệu là (r,c). Trên ô này có một cái cây cao hr,c.

Đàn khỉ muốn chọn một ô làm nhà. Để di chuyển giữa các cây cho thuận tiện, chúng muốn mọi cây nằm cùng hàng hoặc cùng cột với nhà của chúng đều có chiều cao bằng chiều cao của cây ở nhà.

Nói cách khác, nếu đàn khỉ chọn ô (i,j) làm nhà thì điều kiện sau phải đúng: với mọi ô (x,y), nếu (i−x)·(j−y)=0 thì hi,j=hx,y.

Cho kích thước khu rừng và chiều cao của mọi cây, hãy đếm số ô mà đàn khỉ có thể chọn làm nhà.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên t, số bộ test. Tiếp theo là t bộ test, mỗi bộ test gồm:

  • Dòng đầu tiên chứa hai số nguyên n và m (1≤n,m≤1000), kích thước khu rừng.
  • Dòng thứ i trong n dòng tiếp theo chứa m số nguyên hi,1,hi,2,…,hi,m (1≤hi,j≤109), chiều cao của các cây.

Dữ liệu vào đảm bảo tổng các giá trị n trong mọi bộ test không vượt quá 1000, và tổng các giá trị m trong mọi bộ test không vượt quá 1000.

Dữ liệu ra

Với mỗi bộ test, in ra một số nguyên là số ô mà đàn khỉ có thể chọn làm nhà.

Ràng buộc

  • 1≤n,m≤1000; tổng n và tổng m trên mọi bộ test đều không vượt quá 1000.
  • 1≤hi,j≤109.

Ví dụ

Input Output Giải thích
3
1 1
10
2 3
2 5 2
2 2 2
3 3
1 1 1
1 1 1
1 1 1
1
2
9
Ở bộ test thứ nhất, khu rừng chỉ có một cây; đàn khỉ có thể chọn cây đó vì không có cây nào khác. Ở bộ test thứ hai, đàn khỉ có thể chọn ô (2,1) hoặc (2,3). Ở bộ test thứ ba, mọi cây cao bằng nhau nên ô nào cũng chọn được.
2
2 2
1 2
3 4
3 4
5 5 5 5
1 5 2 5
5 5 5 5
0
4
Ví dụ này không có trong đề gốc. Ở bộ test thứ hai, các ô chọn được là (1,2), (1,4), (3,2) và (3,4).

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0