[TẶNG BẠN] TRỌN BỘ Bí kíp học tốt 08 môn
Chắc suất Đại học top - Giữ chỗ ngay!!
ĐĂNG BÀI NGAY để cùng trao đổi với các thành viên siêu nhiệt tình & dễ thương trên diễn đàn.
Bài 4. Đường đi nhiều điểm nhất
Cho một bảng A kích thước MxN (1≤M, N ≤10), trên đó ghi các số nguyên aij (|aij|≤10). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được). Quy tắc đi: Từ ô (i,j)chỉ được quyền sang một trong 3 ô (i, j+1); (i-1, j+1); (i+1, j+1).
Yêu cầu: Hãy tìm vị trí ô xuất phát và một hành trình đi từ cột 1 sang cột N sao cho tổng các số ghi trên đường đi là lớn nhất.
Dữ liệu: Vào từ file văn bản MAX.INP. Trong đó:
- Dòng 1: Ghi hai số M, N là số hàng và số cột của bảng.
- M dòng tiếp theo, dòng thứ i ghi đủ N số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
Kết quả: ghi ra file văn bản MAX.OUT. Trong đó:
- Dòng 1: Ghi số điểm tối đa có được
- N dòng tiếp theo, dòng thứ i ghi chỉ số hàng của ô thứ itrong hành trình. Các số trên 1 dòng trong Input/Output file cách nhau ít nhất một khoản trống
MAX.INP MAX.OUT
[TBODY]
[/TBODY]
Cho một bảng A kích thước MxN (1≤M, N ≤10), trên đó ghi các số nguyên aij (|aij|≤10). Một người xuất phát tại ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được). Quy tắc đi: Từ ô (i,j)chỉ được quyền sang một trong 3 ô (i, j+1); (i-1, j+1); (i+1, j+1).
Yêu cầu: Hãy tìm vị trí ô xuất phát và một hành trình đi từ cột 1 sang cột N sao cho tổng các số ghi trên đường đi là lớn nhất.
Dữ liệu: Vào từ file văn bản MAX.INP. Trong đó:
- Dòng 1: Ghi hai số M, N là số hàng và số cột của bảng.
- M dòng tiếp theo, dòng thứ i ghi đủ N số trên hàng i của bảng theo đúng thứ tự từ trái qua phải
Kết quả: ghi ra file văn bản MAX.OUT. Trong đó:
- Dòng 1: Ghi số điểm tối đa có được
- N dòng tiếp theo, dòng thứ i ghi chỉ số hàng của ô thứ itrong hành trình. Các số trên 1 dòng trong Input/Output file cách nhau ít nhất một khoản trống
MAX.INP MAX.OUT
5 7 | 41 |
9 -2 6 2 1 3 4 0 -1 6 7 1 3 3 8 -2 8 2 5 3 2 1 -1 6 2 1 6 1 7 -2 6 2 1 3 7 | 1 2 3 2 3 4 5 |