JOI 2018 - Deforestation
Xem PDFVương quốc JOI có một khu rừng rộng lớn hình chữ nhật, được chia thành lưới gồm \(H\) hàng theo hướng bắc - nam và \(W\) cột theo hướng đông - tây. Ô ở hàng thứ \(i\) tính từ phía bắc, cột thứ \(j\) tính từ phía tây có \(A_{i,j}\) cây, với \(1 \le i \le H\), \(1 \le j \le W\). Riêng ô ở góc tây bắc có một nhà máy chế biến gỗ và không có cây, tức là \(A_{1,1}=0\).
Chỉ có thể đi vào những ô không có cây. Từ một ô, người ta có thể đi sang ô kề theo hướng đông, tây, nam hoặc bắc nếu ô đó không có cây. Không được đi ra ngoài khu rừng. Là một công trình công cộng của vương quốc, JOI muốn chặt cây để có thể đi lại giữa ô ở góc tây bắc và ô ở góc đông nam.
Ban đầu, JOI đứng ở ô góc tây bắc, nơi có nhà máy chế biến gỗ. JOI có thể đi sang một ô kề theo một trong bốn hướng nếu ô đó không có cây, mất \(1\) phút. JOI cũng có thể đứng tại ô hiện tại và chặt một cây trong một ô kề theo một trong bốn hướng, mất \(1\) phút.
Sau mỗi lần chặt một cây, JOI phải mang cây vừa chặt về nhà máy ở ô góc tây bắc. Tốc độ di chuyển không thay đổi khi mang cây, nhưng trong lúc mang cây, JOI không thể chặt cây khác.
Hãy tìm thời gian ít nhất để chặt cây sao cho hai ô góc tây bắc và đông nam có thể đi lại được với nhau. Thời gian được tính đến khi JOI đã mang cây cuối cùng được chặt về nhà máy.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên \(H,W\).
- Trong \(H\) dòng tiếp theo, dòng thứ \(i\) chứa \(W\) số nguyên \(A_{i,1},A_{i,2},\ldots,A_{i,W}\).
Dữ liệu ra
In ra trên một dòng thời gian ít nhất, tính bằng phút, để thực hiện yêu cầu.
Ràng buộc
- \(1 \le H \le 30\).
- \(1 \le W \le 30\).
- \((H,W) \ne (1,1)\).
- \(0 \le A_{i,j} \le 10000\) với mọi \(1 \le i \le H\), \(1 \le j \le W\).
- \(A_{1,1}=0\).
Phân nhóm
- Nhóm 1 (15 điểm): \(1 \le H \le 5\) và \(1 \le W \le 5\).
- Nhóm 2 (28 điểm): \(A_{i,j} \le A_{i,j+1}\) với mọi \(1 \le i \le H\), \(1 \le j \le W-1\); đồng thời \(A_{i,j} \le A_{i+1,j}\) với mọi \(1 \le i \le H-1\), \(1 \le j \le W\).
- Nhóm 3 (57 điểm): Không có ràng buộc bổ sung.
Ví dụ
Ví dụ 1
Input
2 3
0 1 2
3 4 5Output
32Giải thích
Ký hiệu ô ở hàng thứ \(i\) tính từ phía bắc, cột thứ \(j\) tính từ phía tây là \((i,j)\).
Trước tiên, chặt cây ở \((1,2)\), mất \(1\) phút.
Tiếp theo, chặt hết cây ở \((1,3)\). Để chặt một cây, từ \((1,1)\) đi sang phía đông một ô, chặt một cây ở \((1,3)\), rồi đi sang phía tây một ô để trở về \((1,1)\). Mỗi cây mất \(3\) phút, nên bước này mất \(2 \times 3=6\) phút.
Sau đó, chặt hết cây ở \((2,3)\). Để chặt một cây, từ \((1,1)\) đi sang phía đông hai ô, chặt một cây ở \((2,3)\), rồi đi sang phía tây hai ô để trở về \((1,1)\). Mỗi cây mất \(5\) phút, nên bước này mất \(5 \times 5=25\) phút.
Tổng thời gian là \(1+6+25=32\) phút. Không thể đáp ứng yêu cầu trong thời gian ngắn hơn, nên in ra \(32\).
Ví dụ 2
Input
2 5
0 5 0 0 0
0 0 0 9 1Output
13Giải thích
Chỉ cần chặt cây ở ô \((2,5)\).
Ví dụ 3
Input
2 5
0 2 0 0 0
0 0 0 9 1Output
11Giải thích
Trước tiên chặt cây ở ô \((1,2)\), sau đó chặt cây ở ô \((2,5)\).
Nguồn
JOI 2017/2018, vòng loại, bài 5: Deforestation. Đề bài của Ban tổ chức Olympic Tin học Nhật Bản.
Kỳ thi:
- JOI 2017/2018 - Vòng sơ khảo (1 Tháng 1., 2018)
Bình luận