Đường Đi Trên Lưới Sàng
Points
48
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
Uncategorized
Đề 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
Community Discussion