depth first search

Codeforces Round #168 (Div. 2) B. Convex Shape

訳 n*mのグリッドが与えられ、1マスごとに黒色か白色の情報が与えられる。以下の条件を満たすとき凸の図形である。 黒色のマスから隣接する黒色のマスに移動することができ、移動する向きを2回以上変えずに全ての黒色のマスに辿り着くことができる。 与えら…

AOJ 0263 Beat Panel

解法 パネルの状態を持ってメモ化再帰。 dp[i][S] := 今譜面iを見てパネルの状態Sのときの最大の獲得得点 勝手に前回使った運指は使わない(SRM?か何かでそんな感じの問題があったような…)という条件を付け足したことで冷え。 パネルの状態はbitとかvectorと…

AOJ 0531 Paint Color

解法 座標圧縮→dfs(bfs)で領域を埋めていく 座標圧縮しないと、配列でベニヤ板の領域分取ることはできない ソースコード #define FOR(i, a, b) for (int i = (a);i < (b); ++i) #define REP(i, n) FOR(i, 0, n) int w, h, n; int X, Y; bool field[1024][102…

AOJ 0244 Hot Spring Trip

方針 深さ優先探索. 特殊な切符を使って頂点nにたどり着いた時の最小コストがdict[0][n],使わなかったときdict[1][n]です. コード const int INF = 1 << 30; int N, M; int G[100][100]; int dict[2][100]; vector<int> A[100]; //n:今の場所 //c:特殊な切符 //</int>…

AOJ 0220 Binary Digit A Doctor Loved

方針 深さ優先探索です.全探索なので頭悪い解法かなと思いながらもたかだかO(2^12)っぽいので余裕だろーとか思いながらやりました. コード double n; double x[12]; int tmp[12]; int ans[12]; void dfs(int p, double sum) { if(sum > n || p > 12) retur…

AOJ 0033 Ball

友人が解いていたので再び解いてみた. 方針 全探索しました.O(2^10)かな. #include <iostream> #include <vector> #include <algorithm> #include <cstdio> using namespace std; int ball[10]; bool dfs(int i, int prevLeft, int prevRight) { if(i == 10) return true; if(prevLeft < ball[i]) </cstdio></algorithm></vector></iostream>…

AtCoder Regular Contest #006

結果 3完でした。もうちょっとよく考えたらD解けたかもしれないなぁ A - 宝くじ うわぁめんどくさい実装問題だなぁとか思ってクソ汚いコードを提出した。 int e[10]; int l[10]; int main() { int count = 0, b, tmp; for(int i = 0; i < 6; i++) { scanf("%…

SRM 403 TheLuckyNumbers

問題概要 サンプルセット見れば分かる. aとbが与えられる. 4と7で構成されている数の内, [a, b]に存在する数を求める 方針 再帰で4と7をつなぎ合わせていったら解けると予想. 引数にstringを持ってくる. b a d _ a l l o c素直に整数で実装すると通ります. …