Đường Đi Trên Lưới Sàng

Buổi 64 — Contest Chặng 7
Points
48
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề bài

Cho lưới N×M, mỗi ô (i,j) chứa giá trị V[i][j]. Một ô được gọi là "ô nguyên tố" nếu V[i][j] là số nguyên tố. Tìm đường đi ngắn nhất từ (1,1) đến (N,M) (đi 4 hướng: lên, xuống, trái, phải), sao cho đường đi đi qua nhiều ô nguyên tố nhất. Nếu có nhiều đường đi ngắn nhất, chọn đường có nhiều ô nguyên tố nhất.

Đường đi ngắn nhất = ít bước nhất.

Dữ liệu vào

Dòng 1: Hai số nguyên N, M (1 ≤ N, M ≤ 500) N dòng tiếp theo, mỗi dòng M số nguyên V[i][j] (1 ≤ V[i][j] ≤ 10^6)

Dữ liệu ra

Hai số nguyên cách nhau bởi dấu cách: số bước của đường đi ngắn nhất, và số ô nguyên tố tối đa trên đường đi ngắn nhất đó (tính cả ô đầu và ô cuối nếu là nguyên tố).

Ví dụ
Input Output
3 3\n2 4 3\n6 5 8\n7 10 11 4 3
Giới hạn
  • 1 ≤ N, M ≤ 500
  • 1 ≤ V[i][j] ≤ 10^6
Draft saved