CF1301D Time to Run 题解

思维题。

分析

把一个格子视作一个点，每个点的度数都是偶数，所以这是一张欧拉图。而需要走遍整个方格图，可以证明只要 \(k\) 不超过 \(4nm-2n-2m\) 就一定有解。

很明显存在很多种方案，这里我用的方案是：从左上角出发，向右走 \(m-1\) 步到头，再向左走 \(m-1\) 步回来，向下走一步。重复以上步骤，直到走到左下角。然后向右走一步，向上走 \(n-1\) 步到头，向下走 \(n-1\) 步回来。重复上面步骤，直到走到右下角。这时候你会发现你已经走完了这张网格图里的所有边。注意在走的过程中如果步数用完了中断输出答案即可。

代码

#include <bits/stdc++.h>
using namespace std;
namespace Raiden
{
    int const N = 3005;
    int n, m, k, num[N], cnt;
    char ans[N][5];
    signed work()
    {
        cin >> n >> m >> k;
        if (k > 4 * n * m - 2 * n - 2 * m)return cout << "NO" << endl, 0;
        int anss = 0, sum = k;
        cout << "YES" << endl;
        while (k)
        {
            int _min;
            if (sum - k < m - 1)
            {
                _min = min(k, m - 1);
                num[++cnt] = _min;
                ans[cnt][0] = 'R';
            }
            else if (sum - k < 2 * (m - 1))
            {
                _min = min(k, m - 1);
                num[++cnt] = _min;
                ans[cnt][0] = 'L';
            }
            else if (sum - k < 2 * (m - 1) + 1)
            {
                _min = 1;
                num[++cnt] = _min;
                ans[cnt][0] = 'D';
            }
            else if (sum - k >= 4 * n * m - 2 * n - 2 * m - (n - 1))
            {
                cnt++;
                _min = min(k, n - 1);
                num[cnt] = _min;
                ans[cnt][0] = 'U';
            }
            else if (anss % 3 == 0)
            {
                _min = min(k, m - 1);
                if (_min)
                {
                    cnt++;
                    num[cnt] = _min;
                    ans[cnt][0] = 'R';
                }
                anss++;
            }
            else if (anss % 3 == 1)
            {
                _min = min(k, 3 * (m - 1));
                int __min = _min / 3;
                if (__min)
                {
                    cnt++;
                    num[cnt] = __min;
                    ans[cnt][0] = 'U';
                    ans[cnt][1] = 'D';
                    ans[cnt][2] = 'L';
                }
                if (_min % 3 == 1)
                {
                    num[++cnt] = 1;
                    ans[cnt][0] = 'U';
                }
                if (_min % 3 == 2)
                {
                    num[++cnt] = 1;
                    ans[cnt][0] = 'U';
                    ans[cnt][1] = 'D';
                }
                anss++;
            }
            else
            {
                _min = 1;
                num[++cnt] = _min;
                ans[cnt][0] = 'D';
                anss++;
            }
            k -= _min;
        }
        cout << cnt << endl;
        for (int i = 1; i <= cnt; i++)cout<< num[i] << " " << ans[i] << endl;
        return 0;
    }
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return Raiden::work();
}