DFS
競プロをしているのですが，DFSにまだ慣れないので，備忘録として問題と考え方を残してきたいと思います．
ABC114 C
7, 5, 3の組み合わせの数を求める問題です．
考え方としては，以下のように3, 5, 7それぞれを全探索し，[3,5,7]を組み合わせてできるn以下の数字をカウントすれば良いです．
解いたコード
#include <algorithm> #include <cmath> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <utility> #include <vector> #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define INF 1000000000000 #define MOD 1000000007 using namespace std; using ll = long long; vector<ll> ans; ll n; void dfs(ll p) { if (p > n) { return; } if (to_string(p).find("3") != string::npos && to_string(p).find("5") != string::npos && to_string(p).find("7") != string::npos) { ans.push_back(p); } dfs(p * 10 + 3); dfs(p * 10 + 5); dfs(p * 10 + 7); } int main() { cin >> n; dfs(3); dfs(5); dfs(7); cout << ans.size() << endl; return 0; }
わざわざvector<ll> ansにpush_backしたのはデバックのためです．普通にカウントすればいいです．
ATC 001
迷路を探索してゴールを目指す基本問題です． 解き方として，4方向でDFSしながら記録を取り，すでに探索した所や壁，枠外にきた際に戻る感じです．
座標がy,xなところに少し注意しなければいけないかも．
解いたコード
#include <algorithm> #include <cmath> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <utility> #include <vector> #define rep(i, n) for (int i = 0, i##_len = (n); i < i##_len; ++i) #define reps(i, n) for (int i = 1, i##_len = (n); i <= i##_len; ++i) #define rrep(i, n) for (int i = ((int)(n)-1); i >= 0; --i) #define rreps(i, n) for (int i = ((int)(n)); i > 0; --i) #define INF 1000000000000 #define MOD 1000000007 using namespace std; using ll = long long; int h, w; vector<string> field; bool seen[500][500] = {{false}}; void dfs(int y, int x) { if (x < 0 || y < 0 || x >= w || y >= h) return; //out if (field[y][x] == '#') return; // wall if (seen[y][x]) return; // already seen seen[y][x] = true; // 4 directions dfs(y + 1, x); // ↑ dfs(y, x + 1); // → dfs(y - 1, x); // ↓ dfs(y, x - 1); // ← } int main() { cin >> h >> w; field.resize(h); rep(i, h) cin >> field[i]; // find start and end position int start_x, start_y, end_x, end_y; rep(y, h) rep(x, w) { if (field[y][x] == 's') { start_x = x; start_y = y; } else if (field[y][x] == 'g') { end_x = x; end_y = y; } } dfs(start_y, start_x); if (seen[end_y][end_x]) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
ARC061
1 以上 9 以下の数字のみからなる文字列 Sが与えられた時に．+を入れた時の和を計算する問題です．ただし，+が連続してはいけません．+を入れるか入れないかの2択なのでbit全探索を解く方がベターだと思いますが，全探索で練習しました．
以下のように考えました．左から数えて，木の深さに対応する桁に対して+をつけるか付けないかで全探索しました．
解いたコード
#include <algorithm> #include <cmath> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <utility> #include <vector> using namespace std; using ll = long long; int N; ll dfs(string s, int deep, int last, ll left) { // 深さが桁数-1で打ち切り if (deep == N) { return left + stoll(s.substr(last, s.size() - last)); } // depp番目までを数に直す string s_sub = s.substr(last, deep + 1 - last); ll right = stoll(s_sub); auto sum1 = dfs(s, deep + 1, deep + 1, left + right); // yes auto sum2 = dfs(s, deep + 1, last, left); // no return sum1 + sum2; } int main() { string s; cin >> s; N = s.size() - 1; auto ans = dfs(s, 0, 0, 0); cout << ans << endl; return 0; }
参考サイト shoman.hatenablog.com
