QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#700857#49. Counting pathsTheZone50 ✓2ms3856kbC++232.1kb2024-11-02 13:27:352024-11-02 13:27:36

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 13:27:36]
  • 评测
  • 测评结果:50
  • 用时:2ms
  • 内存:3856kb
  • [2024-11-02 13:27:35]
  • 提交

answer

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

int main() {
    int N, M;
    cin >> N >> M;

    // read the map
    vector<vector<char>> map(N, vector<char>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> map[i][j];
        }
    }

    // fill the dp array
    vector<vector<int>> dp(N, vector<int>(M));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            if (map[i][j] == 'X') {
                dp[i][j] = 0;
            } else if (i == 0 && j == 0) {
                dp[i][j] = 1;
            } else if (i == 0) {
                dp[i][j] = dp[i][j-1];
            } else if (j == 0) {
                dp[i][j] = dp[i-1][j];
            } else {
                dp[i][j] = (dp[i-1][j] + dp[i][j-1]) % MOD;
            }
        }
    }

    // output the result
    cout << dp[N-1][M-1] << endl;

    return 0;
}







































































































































































































































































































































































































































































































































































































Details

Tip: Click on the bar to expand more detailed information

Pretests


Final Tests

Test #1:

score: 5
Accepted
time: 0ms
memory: 3852kb

input:

3 4
....
..X.
....

output:

4

result:

ok single line: '4'

Test #2:

score: 5
Accepted
time: 0ms
memory: 3836kb

input:

200 200
...X..X.....X....XXX..X.X.X.X..X......X.X....X.......X........X.XX.X..X....XX..XXXXX.X.XXX..........XX..XXX.XX....X.......XX..X..X...X.XX..XXX.........XX......X...............XX...XX.XX.X...X...XX.XX.
X..X....X.......XXX.XX.....X.XX..XX.X...X.X.XXX....XX...XX..X.X...X.....X.XX.X....X..XXX......

output:

0

result:

ok single line: '0'

Test #3:

score: 5
Accepted
time: 0ms
memory: 3856kb

input:

3 3
.X.
X..
...

output:

0

result:

ok single line: '0'

Test #4:

score: 5
Accepted
time: 0ms
memory: 3780kb

input:

5 5
.....
.....
.....
.....
.....

output:

70

result:

ok single line: '70'

Test #5:

score: 5
Accepted
time: 0ms
memory: 3608kb

input:

10 10
..........
..........
.....X....
..........
..........
...X......
..........
X.........
.......X..
..........

output:

18238

result:

ok single line: '18238'

Test #6:

score: 5
Accepted
time: 0ms
memory: 3660kb

input:

30 20
....................
....................
....................
....................
....................
....................
....................
....................
....X...............
....................
....................
....................
....................
....................
...

output:

833886024

result:

ok single line: '833886024'

Test #7:

score: 5
Accepted
time: 0ms
memory: 3816kb

input:

10 10
....X..XX.
.X.X.X.XX.
.XX..XXXX.
XX....XXX.
XXXX.X.X.X
.XX.XX...X
.X.XX..X..
XXX....X.X
..XX.XXXX.
X...X.....

output:

0

result:

ok single line: '0'

Test #8:

score: 5
Accepted
time: 1ms
memory: 3840kb

input:

100 100
...X.....X..X...X..XX.....X.X.....X....X......X...XXX..X........XX....X......X......X.X..........XX.
...X.X.X............XXX....X..............X....X....X.X..XX....X.......X...........................X
...XX..............X......X.....X................X.X..XX...X.X..X......XXX.X.....X.X.........

output:

364708889

result:

ok single line: '364708889'

Test #9:

score: 5
Accepted
time: 1ms
memory: 3672kb

input:

100 100
.........X................................................................X..XXX...X................
..............X............X......................X...................X............X........X.......
X..................X..................X...........X......X..........XX...X...................

output:

708504086

result:

ok single line: '708504086'

Test #10:

score: 5
Accepted
time: 2ms
memory: 3760kb

input:

200 200
.....X......X.XX..X.X..X.....X....X.......X.X.............X.X........X.X..........X.X.X.....X........XXXX.....XX..X.......X....XXX.X..X........X..X..X.....X...XX......X.X....................X.........
XX.XX.......X..XXX........XX...............X......X........X.X.......X........X.X.....X.......

output:

0

result:

ok single line: '0'