SRM 242 DIV1 Hard PolyominoCut

SRM

問題 Editorial

問題

width*heightの紙がある。
ここからk-polyominoのどれかを1つだけ切り取りたい。グリッドセルに区切られているその境界線上のみを切ることができる。
ただし切り取った後の紙が連結でなければいけない。
k-polyominoとは、kつのセルで出来ていて、連結であるパターンのことである。
このとき、可能な場合の数を求めよ

  • 1 <= k <= 8
  • k+1 <= width, height <= 800

解答

まずがんばってk-polyominoを列挙する。
次に、座標圧縮的なことをする。
上下左右の角と辺、辺に接していない場所でそれぞれ切ることができるかチェックして、それにその場所の数をかける。
切ることができるかのチェックはdfsをすればいい

コメント

最初問題勘違いしてた。問題文は本当にしっかり読も…それできなきゃ始まらないからね。"Return ..."で書いてあるんだし最低そこだけでもしっかり読もうよ

コード

#include <vector>
#include <algorithm>
#include <set>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
typedef vector<pair<int,int> > vpii;

const int N = 12;
bool paper[N][N];
const int dy[4] = {0,1,0,-1}, dx[4] = {1,0,-1,0};
struct PolyominoCut {
	int k;
	vector<vpii> polyominos;
	//ポリオミノを正規化する。
	//左上が(0,0)となるように平行移動する。
	//あとソートする。ついでに重複してるおかしいのは空でも返しとく
	vpii normalize(const vpii& v) {
		int iy = INF, ix = INF;
		each(i, v) {
			iy = min(iy, i->first), ix = min(ix, i->second);
		}
		vpii r = v;
		each(i, r) i->first -= iy, i->second -= ix;
		sort(all(r));
		if(unique(all(r)) != r.end()) return vpii();
		return r;
	}
	//ポリオミノを列挙する。BFS的にやってる
	void createPolyominos() {
		set<vpii> q, next;
		next.insert(vpii(1, mp(0, 0)));
		rep(i, k-1) {
			q.clear(); q.swap(next);
			each(t, q) if(!t->empty()) {
				vpii u = *t; u.pb(mp(INF, INF));
				each(j, *t) {
					rep(d, 4) {
						u.back() = mp(j->first+dy[d], j->second+dx[d]);
						next.insert(normalize(u));	//normalizeが空を返すのをそのままinsertしてるから別に除去してる
					}
				}
			}
		}
		next.erase(vpii());
		polyominos.assign(all(next));
	}
	int dfs(int y, int x) {
		if(y < 0 || y >= N || x < 0 || x >= N || paper[y][x]) return 0;
		paper[y][x] = true;
		int r = 1;
		rep(d, 4) r += dfs(y + dy[d], x + dx[d]);
		return r;
	}
	//このポリオミノをN*Nの紙から(y,x)で切り取ったときに連結になっているか？
	bool canCut(int y, int x, const vpii& polyomino) {
		mset(paper, 0);
		each(i, polyomino) paper[y + i->first][x + i->second] = true;
		rep(i, N) rep(j, N) if(!paper[i][j]) {
			return dfs(i, j) + polyomino.size() == N*N;
		}
	}
	int count(int k_, int width, int height) {
		k = k_;
		createPolyominos();
		int r = 0;
		//数える。上下左右・回転の対称性を生かして、
		//角と辺と真ん中ひとつを全部で確認したらあとは適当に、という数え方(rng_58さんのコード)もある
		each(p, polyominos) {
			int h = 0, w = 0;
			each(i, *p) h = max(h, i->first + 1), w = max(w, i->second + 1);
			r += 1 * canCut(0, 0, *p);	//up left corner
			r += 1 * canCut(0, N - w, *p);	//up right corner
			r += 1 * canCut(N - h, 0, *p);	//bottom left corner
			r += 1 * canCut(N - h, N - w, *p);	//bottom right corner
			r += (width - w - 1) * canCut(0, 1, *p);	//up side
			r += (width - w - 1) * canCut(N - h, 1, *p);	//bottom side
			r += (height - h - 1) * canCut(1, 0, *p);	//left side
			r += (height - h - 1) * canCut(1, N - w, *p);	//right side
			r += (width - w - 1) * (height - h - 1) * canCut(1, 1, *p);	//center
		}
		return r;
	}
};