yukicoder : No.2675 KUMA

あいにく本番参加はあんまりできず。
https://yukicoder.me/problems/no/2675

問題

無限に大きなグリッド上にN個の駒がある。
このグリッド上に、いくつか桂馬を4方向任意の向きで置き、全駒に対しいずれかの桂馬を1手動かして到達できるようにしたい。
ただし、1つのマスに複数の駒や桂馬を置いてはならない。
最小何個の桂馬を置けば条件を満たせるか。

解法

各駒に対し、桂馬の置ける位置は高々8通りしかない。
bitdpの要領で、各桂馬を置いた場合にカバーされる駒のbitmaskとその最小桂馬数を計算していこう。
同じマスに、向きの異なる複数の桂馬を置けない点に注意。

int N;
int X[16],Y[16];

map<pair<int,int>,int> M[4];
map<int,vector<int>> C;
set<int> S;
int mi=1010;
int dp[1<<16];


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		M[0][{X[i]-2,Y[i]-1}]|=1<<i;
		M[0][{X[i]-2,Y[i]+1}]|=1<<i;
		M[1][{X[i]+2,Y[i]-1}]|=1<<i;
		M[1][{X[i]+2,Y[i]+1}]|=1<<i;
		M[2][{X[i]-1,Y[i]-2}]|=1<<i;
		M[2][{X[i]+1,Y[i]-2}]|=1<<i;
		M[3][{X[i]-1,Y[i]+2}]|=1<<i;
		M[3][{X[i]+1,Y[i]+2}]|=1<<i;
	}
	FOR(j,4) FORR2(a,b,M[j]) {
		FOR(i,N) if(a.first==X[i]&&a.second==Y[i]) break;
		if(i==N) {
			C[a.first*2000+a.second].push_back(b);
		}
	}
	int mask;
	FOR(mask,1<<N) dp[mask]=1010;
	dp[0]=0;
	FORR2(a,b,C) {
		for(mask=(1<<N)-1;mask>=0;mask--) {
			FORR(v,b) chmin(dp[mask|v],dp[mask]+1);
		}
	}
	
	if(dp[(1<<N)-1]==1010) dp[(1<<N)-1]=-1;
	cout<<dp[(1<<N)-1]<<endl;
}

まとめ

最初変な実装をしてしまい遠回りしてしまった。