hyz's blog
0%

CF 1023E Down or Right 题解

发表于

题意

已知一个n×n$(2 <= n <= 500)$的迷宫中存在一条(1, 1)到达(n, n)的路径，行走方向只能是向下或向右。现在需要你通过不超过$4*n$次的询问找出这条路径，注意每次询问的两个点曼哈顿距离不能小于$n-1$。
具体交互规则请参考原题。

分析

注意到次对角线一定存在一点可同时到达(1, 1)和(n, n)，因此，问题转化成了找(1, 1)到达这一点的路径以及这一点到达(n, n)的路径的问题。
具体来说，我们首先固定(n, n)，然后从(1, 1)出发，不断询问下边一点和右边一点能否到达(n, n)，通过$n-1$次询问即可到达次对角线上的一点。同理，我们可以再找出从(n, n)到次对角线上一点的路线。为了保证(1, 1)和(n, n)到达的次对角线的位置是相同的，我们需要让从(1, 1)出发的路线尽可能往下走，然后从(n, n)出发的路线尽可能地往左走。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define x first
#define y second
#define ok cout << "ok" << endl;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const long double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const double Eps = 1e-7;
const int N = 1e5+9;

int n, a[509][509], x, y;
pii pre[509][509];
string s;

bool ask(int x, int y, int xx, int yy) {
    cout << "? " << x << " " << y << " " << xx << " " << yy << endl;
    cin >> s;
    return s[0] == 'Y';
}

int main(void) {
    if(fopen("in", "r")!=NULL) {freopen("in", "r", stdin); freopen("out", "w", stdout);}
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    x = 1, y = 1;
    for(int i = 1; i < n; i++) {
        if(ask(x + 1, y, n, n)) {
            x++;
            a[x][y]++;
            pre[x][y] = pii(x - 1, y);
        }
        else {
            y++;
            a[x][y]++;
            pre[x][y] = pii(x, y - 1);
        }
    }
    string ans;
    while(!(x == 1 && y == 1)) {
        if(pre[x][y].x == x) {
            y--;
            ans += 'R';
        }
        else {
            x--;
            ans += 'D';
        }
    }
    reverse(ans.begin(), ans.end());
    x = n, y = n;
    for(int i = 1; i < n; i++) {
        if(ask(1, 1, x, y - 1)) {
            y--;
            a[x][y]++;
            pre[x][y] = pii(x, y + 1);
        }
        else {
            x--;
            a[x][y]++;
            pre[x][y] = pii(x + 1, y);
        }
    }
    while(!(x == n && y == n)) {
        if(pre[x][y].x == x) {
            y++;
            ans += 'R';
        }
        else {
            x++;
            ans += 'D';
        }
    }
    cout << "! " << ans << endl;

    return 0;
}