Fork Copy Cho một ma trận kích cỡ Mx5 (M <= 12) là bản đồ của một khu vực, bao gồm ô số 0 là đường phẳng và ô số 1 là đá. Một xe tăng đi từ ô chính giữa hàng cuối cùng lên trên cùng của bản đồ, xe tăng có thể đi được theo 3 hướng: lên trên, sang trái, sang phải và không được đi lại ô đã từng đi. Biết rằng khi đi vào đá xe tăng sẽ bị trừ 1 điểm, đi vào đường phẳng sẽ được cộng 1 điểm. Xe tăng sẽ dừng lại khi đi tới hàng trên cùng. Ví dụ: 1 0 0 (0) 1 Xe tăng sẽ bắt đầu đi từ vị trí số 0 màu đỏ, nếu đi theo đường màu 1 1 1 (0) 1 xanh sẽ được 4 điểm. 1 1 1 (1) 1 1 0 0 (0) 1 0 0 (0) (0) 0 1 1 1 (0) 1 Nếu đi theo đường màu cam số điểm sẽ là 6 điểm. 1 0 (0) 0 0 1 1 1 (1) 1 0 0 0 (0) (0) 1 0 (0) (0) (0) Trên xe tăng được trang bị một quả bomb, khi dùng quả bomb này thì 3 dòng liên tiếp hướng lên trên tính từ vị trí xe tăng tất cả đá sẽ vỡ và đường sẽ trở thành đường phẳng. Ví dụ: 1 1 0 0 1 1 1 0 0 1 0 0 0 0 1 0 0 0 0 1 Sau khi nổ bản đồ sẽ thành như hình. 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 (0) 1 0 0 0 (0) 0 0 1 0 0 1 1 1 0 0 1 1 Input. Dòng đầu tiên là số lượng testcase. Tiếp theo là mỗi test. Đầu tiên là số N và tiếp theo là ma trận Nx5. Output. In ra số điểm cao nhất. Ex: 2 5 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 1 0 0 0 0 1 7 1 1 1 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 #1 15 #2 20