Các lượt nộp
    Danh sách bài
    Trang chủ
    Báo lỗi

    solution

    Đề bài: [C] Đếm đường đi giao hàng trong lưới có chướng ngại

    Bản đồ kho hàng là lưới m×nm \times nm×n. Robot xuất phát từ (0,0)(0, 0)(0,0), đích là (m−1,n−1)(m-1, n-1)(m−1,n−1), mỗi bước chỉ đi xuống hoặc sang phải. Ô có giá trị 111 là chướng ngại (không đi qua), ô 000 đi được.

    Hãy đếm số đường đi hợp lệ, lấy modulo 109+710^9 + 7109+7.

    Ví dụ lưới 3×33 \times 33×3 với chướng ngại ở (1,1)(1, 1)(1,1) có 222 đường đi.

    • Định dạng đầu vào:

      Dòng 1: mmm, nnn. Tiếp theo mmm dòng, mỗi dòng nnn giá trị 000 hoặc 111.

    • Ràng buộc đầu vào:

      1≤m,n≤1001 \le m, n \le 1001≤m,n≤100. Ô (0,0)(0,0)(0,0) và (m−1,n−1)(m-1,n-1)(m−1,n−1) luôn là 000.

    • Định dạng đầu ra:

      Một số nguyên — số đường đi modulo 109+710^9 + 7109+7.

    Ví dụ:

    Đầu vào:

    3 3
0 0 0
0 1 0
0 0 0

    Đầu ra:

    2

    Giải thích:

    Hai đường: phải-phải-xuống-xuống và xuống-xuống-phải-phải.

    Đang tải editor...