実装方針によっては、ゴール \((a, b)\) が盤面の端にある場合などに対する場合分けが複雑になるため注意が必要です。

ここでは、複雑な場合分けをできるだけ免れるために、 与えられた問題をサイズがより小さい問題に帰着して再帰的に解く方針を取ります。

(1) \(H = 2\) のとき

次の図に示すようなツアーを構成すれば良いです。

すなわち、

\((1, 1) \rightarrow (2, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow \cdots \rightarrow (1, b-1) \rightarrow (2, b-1) \rightarrow (3-a, b) \rightarrow\)

に続けて

\(\rightarrow (1, b+1) \rightarrow (1, b+2) \rightarrow \cdots \rightarrow (1, W) \rightarrow (2, W) \rightarrow (2, W-1) \rightarrow \cdots \rightarrow (2, b+1) \rightarrow (a, b)\)

とキングを動かします。

(2) \(H > 2\) かつ \(W=2\) のとき

行と列の役割を交換することにより、上記「(1) \(H=2\) のとき」に帰着できます。

(3) \(H > 2\) かつ \(W>2\) のとき

次の図に示す \(S\) の領域にゴール \((a, b)\) があるかないかで場合分けします。

すなわち、

\(S := \lbrace (1, 1), (2, 1) (3, 1), \ldots, (H, 1), (H, 2) \rbrace\)

として、\((a, b) \in S\) かどうかで場合分けします。

・ \((a, b) \not\in S\) のとき

\((1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow \cdots \rightarrow (H, 1) \rightarrow (H, 2)\)

とキングを動かすと、その後「 \((H, 2)\) から始めて、残りのマスをすべて通って、最後に \((a, b)\) に辿り着くようにキングを動かす」問題に帰着されます。 よって、盤面から \(1\) 列目を取り除き、盤面の上下を反転することで、元の問題より \(W\) が \(1\) 小さい問題に帰着できます。

・ \((a, b) \in S\) のとき

行と列の役割を交換することにより、上記「 \((a, b) \not\in S\) のとき」に帰着できます。

C++ 言語による実装例を以下に記載します。

#include <iostream>
#include <utility>
#include <vector>
using namespace std;
typedef pair<int, int> P;

vector<P> solve(int h, int w, int a, int b)
{
	vector<P> ret;
	if(h == 2){
		for(int i = 1; i <= b-1; i++) ret.push_back(P(1, i)), ret.push_back(P(2, i));
		ret.push_back(P(3-a, b));
		for(int i = b+1; i <= w; i++) ret.push_back(P(1, i));
		for(int i = w; i >= b+1; i--) ret.push_back(P(2, i));
		ret.push_back(P(a, b));
	}
	else if(h > 2 && w == 2 || b == 1 || a == h && b == 2){
		ret = solve(w, h, b, a);
		for(auto &p : ret) swap(p.first, p.second);
	}
	else{
		for(int i = 1; i <= h; i++) ret.push_back(P(i, 1));
		vector<P> res = solve(h, w-1, h+1-a, b-1);
		for(auto &p : res) p.first = h+1-p.first, p.second++;
		ret.insert(ret.end(), res.begin(), res.end());
	}
	return ret;
}

int main(void)
{
	int h, w, a, b;
	cin >> h >> w >> a >> b;
	vector<P> ans = solve(h, w, a, b);
	for(auto p : ans) cout << p.first << " " << p.second << endl;
	return 0;
}