diff options
Diffstat (limited to 'introductory_problems')
-rw-r--r-- | introductory_problems/grid_paths.cpp | 47 | ||||
-rw-r--r-- | introductory_problems/readme.md | 7 |
2 files changed, 54 insertions, 0 deletions
diff --git a/introductory_problems/grid_paths.cpp b/introductory_problems/grid_paths.cpp new file mode 100644 index 0000000..778a344 --- /dev/null +++ b/introductory_problems/grid_paths.cpp @@ -0,0 +1,47 @@ +// 1625. Grid Paths +#include <bits/stdc++.h> +using namespace std; + +const int n = 7; +int ans; +char c[n * n + 1]; +bool vis[n + 1][n + 1]; + +bool inbound(int x, int y) { return 1 <= x && x <= n && 1 <= y && y <= n; } + +void dfs(int x, int y, int i) { + if (i == n * n - 1 || (x == n && y == 1)) { + ans += (i == n * n - 1 && (x == n && y == 1)); + return; + } + if ((!inbound(x + 1, y) || vis[x + 1][y]) && + (!inbound(x - 1, y) || vis[x - 1][y])) + if (inbound(x, y - 1) && !vis[x][y - 1] && inbound(x, y + 1) && + !vis[x][y + 1]) + return; + if ((!inbound(x, y + 1) || vis[x][y + 1]) && + (!inbound(x, y - 1) || vis[x][y - 1])) + if (inbound(x + 1, y) && !vis[x + 1][y] && inbound(x - 1, y) && + !vis[x - 1][y]) + return; + vis[x][y] = true; + if (c[i] == 'D' || c[i] == '?') + if (inbound(x + 1, y) && !vis[x + 1][y]) + dfs(x + 1, y, i + 1); + if (c[i] == 'U' || c[i] == '?') + if (inbound(x - 1, y) && !vis[x - 1][y]) + dfs(x - 1, y, i + 1); + if (c[i] == 'R' || c[i] == '?') + if (inbound(x, y + 1) && !vis[x][y + 1]) + dfs(x, y + 1, i + 1); + if (c[i] == 'L' || c[i] == '?') + if (inbound(x, y - 1) && !vis[x][y - 1]) + dfs(x, y - 1, i + 1); + vis[x][y] = false; +} + +int main() { + scanf(" %s", c); + dfs(1, 1, 0); + printf("%d\n", ans); +} diff --git a/introductory_problems/readme.md b/introductory_problems/readme.md index 0046f00..8d11138 100644 --- a/introductory_problems/readme.md +++ b/introductory_problems/readme.md @@ -97,3 +97,10 @@ Consider an infinite string that consists of all positive integers in increasing **Input**: The first input line has an integer `q`: the number of queries. After this, there are `q` lines that describe the queries. Each line has an integer `k`: a 1-indexed position in the string. (Example: 3 7 19 12) **Output**: For each query, print the corresponding digit. (Example: 7 4 1) + +### Grid Paths +There are 88418 paths in a 7 * 7 grid from the upper-left square to the lower-left square. Each path corresponds to a 48-character description consisting of characters D (down), U (up), L (left), and R (right). You are given a description of a path which may also contain certain characters ? (any direction). Your task is to calculate the number of paths that match the description. + +**Input**: The only input line has a 48-character string of characters ?, D, U, L, and R. (Example: ??????R??????U??????????????????????????LD????D?) + +**Output**: Print one integer: the total number of paths. (Example: 201) |