Độ khó: Trung bình (2/4 điểm)

📖 Bài giải chi tiết: 👉 Bấm vào đây để xem lời giải cụ thể của bài này trên blog

⚠️ Lưu ý: hãy đảm bảo em đã thật sự cố gắng tự làm bài trước, rồi mới bấm vào xem bài giải nhé!

🎓 Khóa học Lập trình Thuật toán thi đấu của thầy Nguyễn Việt Nam Sơn – 111 buổi video, kèm cặp cá nhân, luyện thi chuyên Tin · HSG Tin học · Tin học trẻ · đội tuyển quốc gia · Olympic/ICPC. 👉 Xem chi tiết khóa học · Thành tích học viên

📞 Đăng ký học: Zalo 0767 666 702 · Facebook Nguyễn Việt Nam Sơn · 🌐 laptrinhthuattoan.blogspot.com

Bài toán được chuyển sang dạng nhập/xuất chuẩn (stdin/stdout), mỗi file dữ liệu gồm nhiều bộ test.

Cho ma trận grid kích thước ~rows \times cols~. Ban đầu bạn đứng ở góc trên bên trái ~(0, 0)~, và ở mỗi bước bạn chỉ được đi sang phải hoặc đi xuống trong ma trận.

Trong tất cả các đường đi bắt đầu từ góc trên bên trái ~(0, 0)~ và kết thúc ở góc dưới bên phải ~(rows - 1, cols - 1)~, hãy tìm đường đi có tích không âm lớn nhất. Tích của một đường đi là tích của tất cả các số nguyên trong các ô mà đường đi đi qua.

In ra tích không âm lớn nhất modulo ~10^9 + 7~. Nếu tích lớn nhất là số âm thì in ra -1.

Lưu ý rằng phép lấy modulo được thực hiện sau khi đã tìm được tích lớn nhất.

Dữ liệu vào

• Dòng đầu tiên gồm số nguyên ~T~ là số bộ test.
• Mỗi bộ test gồm: dòng đầu chứa hai số nguyên ~rows~ và ~cols~; ~rows~ dòng tiếp theo, mỗi dòng gồm ~cols~ số nguyên là một hàng của ma trận grid.

Kết quả

• In ra ~T~ dòng, dòng thứ ~i~ là kết quả của bộ test thứ ~i~.

Giới hạn

• ~1 \le T \le 10~.
• ~1 \le rows, cols \le 15~.
• ~-4 \le~ grid[i][j] ~\le 4~.

Sample Input 1

4
3 3
-1 -2 -3
-2 -3 -3
-3 -3 -2
3 3
1 -2 1
1 -2 1
3 -4 1
2 2
1 3
0 -4
3 4
1 4 4 0
-2 0 0 1
1 -1 1 1

Sample Output 1

-1
8
0
2

Giải thích

• Bộ test 1: không thể có tích không âm trên đường đi từ ~(0, 0)~ đến ~(2, 2)~, nên in ra ~-1~.
• Bộ test 2: tích không âm lớn nhất là ~1 \times 1 \times (-2) \times (-4) \times 1 = 8~.
• Bộ test 3: tích không âm lớn nhất là ~1 \times 0 \times (-4) = 0~.
• Bộ test 4: tích không âm lớn nhất là ~1 \times (-2) \times 1 \times (-1) \times 1 \times 1 = 2~.

Nguồn: LeetCode 1594.