棋盘大小为 ,有一个王在 。每一步可以走到八连通的格子之一。构造一种方案,使得王经过所有格子,并停在 。
。
(1) 若 ,那么可以这样走:

(2) 若 且 ,那么可以交换行列,变成情况 (1)。
(3) 若 且 ,那么可以这样走:

这样可以消掉第一列,递归处理 。
但是有一些特殊情况,若 或者 且 即终点在浅绿色的格子里,那么就不能这样消去一行,需要转换行列之后消去第一列。
部分代码:
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();
}