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

Xem PDF
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
    minhtuanitk20    8:16 p.m. 28 Tháng 9, 2021

    Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.


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

      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 phản hồi

      • -13
        ekhoavvdd    2:51 p.m. 14 Tháng 8, 2020

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

        1 phản hồi