C++の練習を兼ねて, Educational DP Contest / DP まとめコンテスト の 問題H (H – Grid 1) を解いてみた.
■感想.
1. 途中の問題は, ほとんど解けてないが, なぜか本問を正答出来たので, アップロードしてみた.
■C++版プログラム(問題H／AC版).
|
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 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const LL MOD = 1e9 + 7; int main() { // 1. 入力情報取得. LL H, W; cin >> H >> W; string A[H]; for(int i = 0; i < H; i++) cin >> A[i]; // 2. 経路数を計算. LL dp[H][W] = {}; // ゴール地点を, 1通りで設定. dp[H - 1][W - 1] = 1; for(LL i = H - 1; i >= 0; i--){ for(LL j = W - 1; j >= 0; j--){ string s = A[i]; // 右. if(j < W - 1){ string s = A[i]; if(s[j] == '.' && s[j + 1] == '.') dp[i][j] = dp[i][j + 1], dp[i][j] %= MOD; } // 下. if(i < H - 1){ string s = A[i], t = A[i + 1]; if(s[j] == '.' && t[j] == '.') dp[i][j] = dp[i + 1][j], dp[i][j] %= MOD; } // 右 and 下. if(j < W - 1 && i < H - 1){ string s = A[i], t = A[i + 1]; if(s[j] == '.' && s[j + 1] == '.' && t[j] == '.'){ dp[i][j] = dp[i][j + 1] + dp[i + 1][j], dp[i][j] %= MOD; } } } } // for(LL i = 0; i < H; i++){ // for(LL j = 0; j < W; j++){ // cout << dp[i][j] << " "; // } // cout << endl; // } // 3. 後処理. cout << dp[0][0] << endl; return 0; } |
|
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 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
[入力例] 3 4 ...# .#.. .... [出力例(debug版)] 3 2 2 0 1 0 2 1 1 1 1 1 3 ※AtCoderのテストケースより [入力例] 5 2 .. #. .. .# .. [出力例(debug版)] 0 0 0 0 1 0 1 0 1 1 0 ※AtCoderのテストケースより [入力例] 5 5 ..#.. ..... #...# ..... ..#.. [出力例(debug版)] 24 12 0 2 0 12 12 6 2 0 0 6 4 2 0 2 2 2 2 1 0 0 0 1 1 24 ※AtCoderのテストケースより [入力例] 20 20 .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... .................... [出力例] 345263555 ※AtCoderのテストケースより [入力例] 100 100 .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... .................................................................................................... [出力例] 690285631 |