ABC232H King's Tour 做题记录

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

$1 \le h,w \le100$。

(1) 若 $H=2$，那么可以这样走：

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

(3) 若 $H>2$ 且 $W>2$，那么可以这样走：

这样可以消掉第一列，递归处理 $H,W-1,H-A+1,B-1$。

但是有一些特殊情况，若 $B=1$ 或者 $B=2$ 且 $A=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();
}