読者です 読者をやめる 読者になる 読者になる

DFS

AOJ 2163 Tatami

問題 Tatami 1:2の大きさの畳をH,Wの大きさの部屋に敷き詰める方法は何通りあるか。 畳の敷き詰め方のルールに乗っ取って敷き詰めて行きます。 解法 畳を敷き詰めるルールは日本人なら誰でも分かるので説明の必要はありませんね。DFSで全探索すれば解けます…

AOJ 1034 Line Puzzle

問題 Line Puzzle 解法 DFS。左上の起点から順番に走査していく。 心臓に悪いコード int dy[] = {-1,0,1,0}, dx[] = {0,-1,0,1}; int n, used[8][8], p[8][8], res; void dfs(int sum, int y, int x, int rest){ if(res) return; if(sum == 0 && rest == 0){…

AOJ 1108

問題 A Long Ride on a Railway 解法 路線図が与えられる。最長経路の長さとそのパスを表示する。グラフの最長パスを計算するのですが、駅の数が10以下なので全探索でいける。 コード int cost[10][10], ns, nl, res, vres[100], pres; int dfs(int sum, int…

AOJ 2026 Divisor is the Conqueror

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2026) N枚のカードがあったそれを一枚ずつ出していく。出せるのは今までに出した、カードの総和の約数だけ。 解法 DFSで解く。普通に解いても無理だった。逆から解くとできるんだって コー…

AOJ 1103 Board Arrangements for Concentration Games

問題 AからHのカードを並べてく、カードのセットに相対的な位置だけでカウントしていくから AとBのセットをかえても同じ 解法 DFSで解きます。 コード int board[4][4]; int dy[4], dx[4]; int dfs(int n){ if(n >= 8) return 1; int res = 0; int y, x; rep…

AOJ 2011 Gather the Maps!

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2011) 解法 詳しくはhttp://www.deqnotes.net/acmicpc/p0017/。 コード ````cpp int m[64][64], in[64][32]; int main(){ int n, f, day; while(scanf("%d", &n) && n){ memset(m, 0, sizeo…

AOJ 0169 Blackjack

問題 (http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0169) 解法 DFSが楽。あとは1以外を全部足してから1をどうするかってやる。 コード DFS int a[512], p; int dfs(int n, int c){ if(n > 21) return 0; if(c == p) return n; if(a[c] == 1) …

AOJ 2014 Surrounding Area

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2014 日本語。 解法 あるマスからDFSしていって黒に到達したら、1、白に到達したら2って感じにして行く。 dfsの再帰のところを最初+=にしようとしていた コード int f[50][50], c[50][50];…

AOJ 1144 Curling 2.0

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1144&lang=jp 日本語。 解法 DFSで解く。四方向見て、進めるなら進む。盤面の外に行ったら次っていう感じでまわしてく。 コード int w, h; int board[20][20]; int dx[] = {0,-1,0,1}, dy[] …

AOJ 1045 Split Up!

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1045 日本語。 解法 適当にDFSすればできる。 コード int n; int a[128]; int dfs(int p, int g, int c){ if(n == c) return abs(p-g); return min(dfs(p+a[c], g, c+1), dfs(p, g+a[c], c+1…