問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230 解法 幅優先探索（BFS）する はしごを登ったり、滑ったりする処理をミスってバグりまくった #include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef pair<int, int> P; typedef pair<P, int> PP; in</p,></int,></queue></algorithm></cstdio>…

問題 http://poj.org/problem?id=1226解法 全探索したら通った。最小の文字列を選んで計算回数を落としたが別に必要ないっぽい。 #include <cstdio> #include <algorithm> #include <string> #include <iostream> using namespace std; int t, n; int main(){ cin >> t; for(;t > 0; t--){ cin >> </iostream></string></algorithm></cstdio>…

明日、PCK本選です。 がんばります!問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0223解法 地道に幅優先探索する。 #include <cstdio> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef pair<int,int> P; typedef pair<int , pair<P, P> > T; const int INF = 1 </int></int,int></vector></queue></algorithm></cstdio>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0213解法 全探索すればいいらしい。実装キツい。 #include <cstdio> #include <algorithm> using namespace std; typedef pair<int,int> P; const int MAX_N = 15; const int MAX_XY = 10; int N, X, Y; int memo[MAX_N];</int,int></algorithm></cstdio>…

JOI予選のとき、問題文を読む前からあきらめてしまった問題。 今回やってみたら20分でできた。成長したなー。問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0569解法 六角形の移動先配列を持ちながら深さ優先探索 #include <cstdio> #include <algorithm> usi</algorithm></cstdio>…

問題 http://poj.org/problem?id=1915 ナイトの動きで何手で目的地までいけるかを計算せよ解法 BFS 移動先座標を配列で持っておくのがコツ #include <cstdio> #include <algorithm> #include <queue> using namespace std; typedef pair<int,int> P; const int INF = 1 << 29; const int dx[8] =</int,int></queue></algorithm></cstdio>…

解法 座標圧縮+DFS はじめて座標圧縮した。 解説を参考にして解いた #include <cstdio> #include <algorithm> #include <set> using namespace std; const int MAX_N = 1000; int N, h, w; bool a[MAX_N * 2 + 3][MAX_N * 2 + 3]; int dx[4] = { 1, -1, 0, 0}; int dy[4] = { 0, 0, 1</set></algorithm></cstdio>…

問題 解法 構文解析するだけ。 しなくてもできそう。 解析したあとは、再帰で一番上のパネルを求めることができる #include <cstdio> #include <string> #include <vector> #include <algorithm> using namespace std; //タグ class T{ public: string name; int x1, y1, x2, y2; vector<T> ko; //</t></algorithm></vector></string></cstdio>…

問題 '@'から縦横に進んでいけるマスの個数をもとめよ 解法 深さ優先探索をしてもとめる #include <cstdio> #include <algorithm> using namespace std; const int MAX_HW = 20; char a[MAX_HW + 2][MAX_HW + 2]; int H, W, sx, sy; const int dx[] = { -1, 0, 0, 1}; const int</algorithm></cstdio>…

3月になった。そろそろ入学試験というものがあるらしい。 問題 解法 タイルにかかれた指示どおりに移動をシミュレーションをしていけばいい。 ループを検出するためにすでに訪れたタイルを記録しておかなければならない。 過去に一度でも訪れた場所に再び来…

問題 解法 あるマスがまだ区画整理されていなければ、 1,区画の総数に1をたす。 2,区画整理したしるしをつける。 3,隣接するマスが(区画整理されていない&&同じ木の種類)ならば区画整理したしるしをつける。 4, 3を再帰的に行う。 区画整理されていないマス…

問題 解法 幅優先探索する。ジャンプ先の配列を用意しておくと便利。 領域外に出てしまったときの処理を書き忘れていて、すこし手間取った。コード #include <cstdio> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> P; //座標 typedef pair<int, P> Q; //噴水の番</int,></int,></algorithm></queue></cstdio>…

アルゴリズムデザインにのっていた問題。 本当は動的計画法を使うらしいけど、よく分からないので、BFSした。問題 木が与えられる。この木の根から情報を発信する。情報は、時間１の間に各ノードから そのノードの１つの子ノードにしか送ることができない。 …

この前作ったハニカムのやつを少し変えて、あとは幅優先探索する。 いま探索しているところが何ターン目のところなのかを記憶しながら探索していく。 #include <cstdio> #include <queue> #include <algorithm> using namespace std; typedef pair<int, int> P; typedef pair<int, P> D; //ターン数、位置</int,></int,></algorithm></queue></cstdio>…

JOI 予選でハニカム構造が出てきて、手も足も出なかったのでつくってみた。 最初の2つは普通の正方形が並べられている形。 次がハニカム構造。4つめが三角形が敷き詰められた形。 上記のようなときにこれを使って探索とかすると、たぶん便利。 /* 四角形のと…

左上から右下にかけて順番にたどっていき、何個のループがあるか数える。 一度通った場所には印をつけ、ループになっているか確かめながらたどっていくとよい。 #include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 100; int N; typedef pair<int, int> P; P </int,></algorithm></cstdio>…