自动搬运

查看原文

来自洛谷，原作者为

	jijidawang And in that light, I find deliverance.

搬运于2025-08-24 22:48:37，当前版本为作者最后更新于2025-05-19 17:44:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先特判 $W=1$（平凡）。接下来考虑处理箱子在第一行或第一列的情况：首先通过某些手段尝试到达左下角（如果左下角是箱子可以到达任意一个地方），然后一路向上走到头再向右走到头。这样如果最后走到的横坐标不为 $1$ 那么说明第一列上有箱子，且箱子的坐标是容易求出的；否则移动到的位置一定在箱子的左边一格（如果走到了 $(1,W)$，那么说明箱子在左下角）。

然后考虑箱子不在第一行或第一列的情况：考虑一种蛇形的走法（如下图左），

那么第一次途经一个格子一定是从向右或者向下方向进入，如果那里恰好是一个箱子后续的行动就都会被限制在箱子周围（如上图右）。如果令蛇形走法的最后一步是向右的，那么到达的位置右边一格就恰好是箱子的位置。

从而可以在 $2$ 次询问以内找出箱子的位置。

参考实现（可能与文字说明有些许出入）：

int H, W;
int main()
{
	auto ask = [&](string s){int x, y; cout << "? " << s << endl << flush; cin >> x >> y; return make_pair(x, y);};
	auto rp = [&](char c, int k){string s; while (k--) s.push_back(c); return s;};
	cin >> H >> W;
	if (W == 1){int o = ask(rp('v', H)).first + 1; cout << "! " << o << " " << 0 << endl; return 0;}
	string op; op += ">v<";
	for (int L=1; L<=max(H, W); L++) op += "v" + rp('>', L) + rp('^', L + 1) + ">" + rp('v', L + 1) + rp('<', L + 1);
	op += "v" + rp('>', W); pii o = ask(op);
	if (o != make_pair(H - 1, W - 1)){cout << "! " << o.first << " " << o.second + 1 << endl; return 0;}
	op.clear(); op += rp('v', H) + ">vv<" + rp('^', H) + rp('>', W); o = ask(op);
	if (o == make_pair(0, W - 1)){cout << "! " << H - 1 << " " << 0 << endl; return 0;}
	if (o.first){cout << "! " << o.first - 1 << " " << 0 << endl; return 0;}
	cout << "! " << 0 << " " << o.second + 1 << endl;
	return 0;
}