atcoderDP/Grid1.java at master · KTong821/atcoderDP · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
importjava.util.*;
importjava.io.*;

publicclassGrid1 {

publicstaticinth, w;
publicstaticfinalintmod = 1000000007;
publicstaticboolean[][] map;
publicstaticint[][] dp;

publicstaticvoidmain(String[] args) throwsIOException {
BufferedReaderbr = newBufferedReader(newInputStreamReader(System.in));
String[] s = br.readLine().split(" ");
h = Integer.parseInt(s[0]);
w = Integer.parseInt(s[1]);
map = newboolean[h][w];
dp = newint[h][w];

Stringst;
for (inti = 0; i < h; i++) {
st = br.readLine();
for (intj = 0; j < w; j++)
if (st.charAt(j) == '.')
map[i][j] = true;
 }

dp[0][0] = 1;
for (inti = 0; i < h; i++) {
for (intj = 0; j < w; j++) {
intk = i - j;
if (k < 0)
break;
if (!map[k][j])
continue;
if (k - 1 >= 0 && map[k - 1][j]) {
dp[k][j] += dp[k - 1][j];
dp[k][j] %= mod;
 }
if (j - 1 >= 0 && map[k][j - 1]) {
dp[k][j] += dp[k][j - 1];
dp[k][j] %= mod;
 }
 }
 }
for (intj = 1; j < w; j++) {
for (inti = h - 1; i >= 0; i--) {
intk = j + h - i - 1;
if (k == w)
break;
if (!map[i][k])
continue;
if (i - 1 >= 0 && map[i - 1][k]) {
dp[i][k] += dp[i - 1][k];
dp[i][k] %= mod;
 }
if (k - 1 >= 0 && map[i][k - 1]) {
dp[i][k] += dp[i][k - 1];
dp[i][k] %= mod;
 }
 }
 }
// for (int i = 0; i < h; i++) {
// for (int j = 0; j < w; j++)
// System.out.print(dp[i][j] + " ");
// System.out.println();
// }
System.out.println(dp[h - 1][w - 1]);

	}

}