ABC232H King's Tour 做题记录

棋盘大小为 h×wh \times w,有一个王在 (1,1)(1,1)。每一步可以走到八连通的格子之一。构造一种方案,使得王经过所有格子,并停在 (a,b)(a,b)

1h,w1001 \le h,w \le100

(1) 若 H=2H=2,那么可以这样走:

(2) 若 H>2H>2W=2W=2,那么可以交换行列,变成情况 (1)。

(3) 若 H>2H>2W>2W>2,那么可以这样走:

这样可以消掉第一列,递归处理 H,W1,HA+1,B1H,W-1,H-A+1,B-1

但是有一些特殊情况,若 B=1B=1 或者 B=2B=2A=HA=H 即终点在浅绿色的格子里,那么就不能这样消去一行,需要转换行列之后消去第一列。

部分代码:

typedef pair<int,int> P;

int n,m,a,b;

vector<P> dfs(int n,int m,int a,int b)
{
	vector<P> res;
	if(m==2)
	{
		vector<P> tmp=dfs(m,n,b,a);
		for(P u:tmp) res.push_back(P(u.second,u.first));
		return res;
	}
	if(n==2)
	{
		fo(i,1,b-1) res.push_back(P(1,i)),res.push_back(P(2,i));
		fo(i,b,m) res.push_back(P(a==1?2:1,i));
		df(i,m,b) res.push_back(P(a,i));
		return res;
	}
	if(a==1||(b==m&&a==2))
	{
		vector<P> tmp=dfs(m,n,b,a);
		for(P u:tmp) res.push_back(P(u.second,u.first));
	}
	else
	{
		fo(i,1,m) res.push_back(P(1,i));
		vector<P> tmp=dfs(n-1,m,a-1,m-b+1);
		for(P u:tmp) res.push_back(P(u.first+1,m-u.second+1));
	}
	return res;
}

inline void slove()
{
	rd(n),rd(m),rd(a),rd(b);
	vector<P> ans=dfs(n,m,a,b);
	for(P u:ans) wrt(u.first),spe(),wrt(u.second),edl();
}