問題概要 格子状のマス目があり、いくつかに障害物がおかれている。(0,0)から(x,y)への移動の最短距離を求めよ3 解法 BFS 実装(C++) #include <algorithm> #include <iostream> #include <queue> #include <cstring> using namespace std; typedef pair<int,int> P; queue<P> que; int MAP[1010][1010]; int co</p></int,int></cstring></queue></iostream></algorithm>…

問題概要 問題文にある図のようなスライドパズル（0の部分が空）を解け。

問題概要 N( 解法 BitDPする。（10！）なので全探索でも間に合うかも…？ 実装(C++) #include <iostream> #include <algorithm> using namespace std; #define chmin(a,b) a=min((a),(b)) int main(){ int T; cin>>T; while(T--){ int n,x[11],y[11],dp[11][1<<11]; cin>>x[0]>>y[0</algorithm></iostream>…

問題概要 N個の点が与えられる。点間に直線を引いて全ての点同士で移動が可能にする時に最小の線の長さの合計を求めよ。

問題概要 牛に部屋を与えたいが、牛はそれぞれ部屋の希望をいくつかもっており、さらに一つの部屋に一つの牛しか割り当てられない。希望の部屋に割り当てられる牛の数を求めよ。

問題概要 N個の町があり、それぞれを繋ぐ道路を建設するのにかかる費用が与えられる。全ての町が繋がるような最小のコストの木のうち、もっとも高いコストの辺を求めよ

問題概要 二つの文字列の編集距離を求めよ。複数ケースあるので注意 解法 編集距離をDPで求める。 詳しくはレーベンシュタイン距離 - Wikipediaを詳細。 実装(C++) #include <cstdio> #include <iostream> #include <cstring> using namespace std; int n,m; int dp[1001][1001]; char x</cstring></iostream></cstdio>…

問題概要 4x4のスイッチがある.全てのスイッチをOFFにしろ。ただしあるスイッチをクリックするとその列とその行のスイッチ全てが反転される。 解法 単純に全探索だと間に合わないので半分全列挙する。 実装(C++) #include <iostream> #include <algorithm> using namespace std; s</algorithm></iostream>…