Submission #3945570

Source Code Expand

Copy
#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL mod = 1000000007;
LL H, W;
std::vector<std::string>a;
std::vector<std::vector<LL>>memo;

LL dp(LL i, LL j)
{
	if (i == H - 1 && j == W - 1) return 1;
	if (memo[i][j] != -1) return memo[i][j];
	LL res1 = 0, res2 = 0;
	if (i < H - 1) if (a[i + 1][j] == '.') res1 = dp(i + 1, j);
	if (j < W - 1) if (a[i][j + 1] == '.') res2 = dp(i, j + 1);
	return memo[i][j] = (res1 + res2) % mod;
}

int main()
{
	in >> H >> W;
	a.resize(H);
	rep(i, H) in >> a[i];

	memo.resize(H);
	rep(i, memo.size()) memo[i].resize(W, -1);
	out << dp(0, 0) << std::endl;
}

Submission Info

Submission Time
Task H - Grid 1
User Bwambocos
Language C++14 (GCC 5.4.1)
Score 100
Code Size 714 Byte
Status
Exec Time 49 ms
Memory 9344 KB

Test Cases

Set Name Score / Max Score Test Cases
All 100 / 100 0_00, 0_01, 0_02, 0_03, 1_00, 1_01, 1_02, 1_03, 1_04, 1_05, 1_06, 1_07, 1_08, 1_09, 1_10, 1_11
Case Name Status Exec Time Memory
0_00 1 ms 256 KB
0_01 1 ms 256 KB
0_02 1 ms 256 KB
0_03 1 ms 256 KB
1_00 1 ms 256 KB
1_01 1 ms 256 KB
1_02 49 ms 9344 KB
1_03 37 ms 9216 KB
1_04 36 ms 8960 KB
1_05 36 ms 8960 KB
1_06 41 ms 9216 KB
1_07 46 ms 9216 KB
1_08 47 ms 9088 KB
1_09 48 ms 9216 KB
1_10 48 ms 9088 KB
1_11 48 ms 9088 KB