CSES - Grid Paths | Đường đi trên lưới - LQDOJ: Le Quy Don Online Judge

CSES - Grid Paths | Đường đi trên lưới

Tác giả:

Dạng bài

Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Xét một lưới ô vuông kích thước \(n \times n\), trong đó một số ô có thể có bẫy. Ta không được phép đi qua một ô có bẫy.

Hãy tính số lượng đường đi từ góc trên trái đến góc dưới phải của lưới, biết rằng ta chỉ được đi sang phải hoặc đi xuống dưới.

Input

Dòng đầu tiên chứa một số nguyên \(n\): kích thước của lưới.
\(n\) dòng sau, mỗi dòng chứa \(n\) kí tự mô tả lưới: . biểu thị một ô trống và * biểu thị một cái bẫy.

Output

In ra một số nguyên duy nhất là số lượng đường đi chia lấy dư cho \(10 ^ 9 + 7\).

Constraints

\(1 \leq n \leq 1000\)

Example

Sample input

4  
....  
.*..  
...*  
*...

Sample output

Bình luận

long n; cin >> n;
    vector<vector<char>> grid(n, vector<char>(n));
    vector<vector<long>> dp(n, vector<long>(n, 0));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> grid[i][j];
        }
    }
    if (grid[0][0] == '.') dp[0][0] = 1;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == '*') continue; 
            if (i > 0) dp[i][j] = (dp[i][j] + dp[i - 1][j]) % MOD; 
            if (j > 0) dp[i][j] = (dp[i][j] + dp[i][j - 1]) % MOD; 
        }
    }
    cout << dp[n-1][n-1];

Phản hồi

2 bình luận nữa