ROBOT2 - Robot và số nguyên tố
Dữ liệu vào: standard input
Dữ liệu ra: standard output
Giới hạn thời gian: 1.0 giây
Giới hạn bộ nhớ: 128 megabyte
Đăng bởi: trungvt130584

Một bảng hình chữ nhật kích thước là M x N, trong đó các dòng được đánh số thứ tự từ 1 tới M, các cột được đánh số thứ tự từ 1 tới N. Trên mỗi ô ghi một số nguyên dương C[i,j] gọi là độ cao của ô (i,j).

Một Robot cần đi từ vị trí có tọa độ (1,1) tới vị trí có tọa độ (M,N). Từ một ô (i,j) Robot có thể di chuyển sang ô (i+1,j) hoặc ô (i,j+1), sao cho chênh lệnh độ cao giữa hai ô đó là một số nguyên tố.

Một ô (u,v) khác ô (1,1) và (M,N) được gọi là một ô đặc biệt nếu như mọi đường đi từ ô (1,1) tới ô (M,N) luôn phải qua ô (u,v).

Viết chương trình tìm tất cả các ô đặc biệt.

Dữ liệu nhập:

- Dòng 1 ghi 2 số nguyên M và N (1 ≤ M, N ≤ 100)

- M dòng tiếp theo, mỗi dòng ghi N số nguyên dương C[i,j] (C[i,j] ≤ 1000)

Dữ liệu xuất:

- Dòng 1 ghi số K là số lượng ô đặc biệt.

- K dòng tiếp theo, mỗi dòng ghi cặp số u, v là tọa độ của ô đặc biệt. (tọa độ các ô đặc biệt phải được in ra theo thứ tự tăng dần của tọa độ dòng, nếu trùng tọa độ dòng thì tăng dần theo tọa độ cột)

 
 
 

Ví dụ

  • input
    5 6
    1 4 8 6 2 9
    6 9 12 15 8 4
    8 12 2 4 13 4
    7 5 7 9 11 9
    8 6 8 9 14 16
    output
    2
    2 2
    4 5
 
 
 
Back to Top