Đếm đường đi trên ma trận 1

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Xem hướng dẫn
Tác giả:
jumptozero
Dạng bài
Điểm: 400 Thời gian: 2.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho ma trận gồm \(H\) hàng và \(W\) cột. Gọi \((i,j)\) là ô vuông ở hàng thứ \(i\) và cột thứ \(j\).

Với mỗi \(i,j(1\le i\le H,1\le j\le W)\), ô vuông \((i,j)\) được mô tả bởi kí tự \(a_{i,j}\). Nếu \(a_{i,j}=\). thì ô vuông này trống rỗng, nếu \(a_{i,j}=\) # thì ô vuông này chứa vật cản.

\(Kaninho\) bắt đầu ở ô vuông \((1,1)\) và muốn đến ô vuông \((H,W)\) bằng việc lặp lại các bước: Đi sang phải hoặc đi xuống dưới ô trống kề với nó.

Tìm số con đường mà \(Kaninho\) có thể đi được từ ô \((1,1)\) đến ô \((H,W)\). Bởi vì đáp án có thể lớn, nên trước khi in ra cần lấy mod \(10^9+7\).

Input

  • Dòng thứ nhất chứa hai số nguyên \(H,W(2\le H,W\le 1000)\)

  • \(H\) dòng tiếp theo, mỗi dòng chứa \(W\) kí tự \(a_{i,1},a_{i,2},...,a_{i,W}(1\le i\le H)\) - thể hiện ma trận \(Kaninho\) cần đi. Biết rằng đề ra luôn đảm bảo các ô \((1,1)\) và \((H,W)\) đều trống.

Output

  • In ra đáp án cần tìm.

Example

Test 1

Input 
3 4
...#
.#..
....
Output 
3
Note

Bình luận


  • 9
    N7hoatt    9:49 a.m. 17 Tháng 8, 2020 ← chỉnh sửa 3

    HINT

    • đầu tiên ta tạo mảng hai chiều \(dp\) để lưu vị trí của các ô vuông, ta tạo mảng hai chiều \(f\) để lưu số cách đi đến ô \(dp[i][j]\)
    • ta có công thức quy hoạch động:

    \(f[0][1]=1\)

    nếu \(dp[i][j]=\) \('\)#\('\) thì \(f[i][j]=0\)

    nếu \(dp[i][j]=\) \('\).\('\) thì \(f[i][j]=(f[i-1][j]+f[i][j-1])\)%\(1e9+7\)

    kết quả là \(f[h][w]\)

    Reference AC code | \(O(h*w)\)time | \(O(h*w)\)space | DP-general

    int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    f[0][1]=1;
    cin>>h>>w;
    for(int i=1; i<=h; ++i)
    {
        for(int j=1; j<=w; ++j)
        {
            cin>>dp[i][j];
            f[i][j]=((dp[i][j]=='#') ? 0 : (f[i-1][j]+f[i][j-1])%mod);
        }
    }
    cout<<f[h][w];
}


    • 2
      VoBaThongL921    2:37 p.m. 10 Tháng 10, 2021

      Bạn có thể chỉ cần khai báo 1 biến char để nhận kí tự chứ không cần mảng dp 2 chiều đó


      • 2
        VoBaThongL921    7:40 p.m. 29 Tháng 8, 2021

        Bạn giải thích thêm cho mình phần công thức f[i-1][j]+f[i][j-1] được không ?. Cảm ơn bạn nhé


        • 1
          N7hoatt    2:07 p.m. 31 Tháng 8, 2021

          số bước đến f[i][j] sẽ là tổng của số bước đến f[i-1]j và f[i]j-1

      2 bình luận nữa