問題概要 （略） 考え方 最短経路問題．与えられる入力の形を上手く生かしてBFSすることが出来る．計算量はO(WH)となる． 実装(C++) #include <iostream> #include <vector> #include <sstream> #include <algorithm> #include <queue> #include <cstring> using namespace std; #define REP(i,x)for(int i=0;i<(int</cstring></queue></algorithm></sstream></vector></iostream>…

問題概要 （略） 解説 0番目の正方形の位置を(0,0)として，全ての正方形の位置を求める．幅は，最も右にある正方形と最も左にある正方形のx座標の差+1となり，高さは，最も上にある正方形と最も下にある正方形のy座標の差+1となる．計算量はO(N)となる． 実…

問題概要 10x10の領域に半径1の点をN個置く。任意の位置にある半径1の円に最大で何個入るかを求めろ。 解法 分割統治法を用い、探索領域を減らしていく。 AOJ0090と全く同じ問題。 実装(C++) #include <cstdio> #include <queue> #include <algorithm> #include <vector> #include <iostream> using names</iostream></vector></algorithm></queue></cstdio>…

問題概要 10x10の領域に中心が入るように半径1の円をN個置く。最大で何個重なっているかを求めろ。 解法 分割統治法を用い、探索領域を減らしていく。 詳しい解説はプログラム・プロムナードを参照。 実装(C++) #include <cstdio> #include <queue> #include <algorithm> #include <vector> #in</vector></algorithm></queue></cstdio>…