summaryrefslogtreecommitdiff
path: root/introductory_problems/grid_paths.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-02-20 09:50:31 -0700
committerJack Sangdahl <[email protected]>2025-02-20 09:50:31 -0700
commit844264c0bc2777d0e952196ab383f1dc004e6f81 (patch)
tree3574e6c1c29557e3c05af6e698da419c0bdb9ad3 /introductory_problems/grid_paths.cpp
parent91491fa92ae64f36e8277849d0943d20b82093bc (diff)
downloadcses-844264c0bc2777d0e952196ab383f1dc004e6f81.tar.gz
cses-844264c0bc2777d0e952196ab383f1dc004e6f81.zip
1625. grid paths
Diffstat (limited to 'introductory_problems/grid_paths.cpp')
-rw-r--r--introductory_problems/grid_paths.cpp47
1 files changed, 47 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);
+}