>v<

jijidawang · 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;
}