url: http://oj.ecustacm.cn/problem.php?id=1455

tag: 搜索

思路：使用bfs或者dfs。如果使用bfs需要将每次的路径也放入队列中，当搜到终点时，就直接将答案输出。使用dfs需要使用一种记忆化的剪枝技巧，每次判断当前的路径长度 + 1和即将到达的那个点的到那个点的最短的长度比较，如果大于就直接跳过，如果小于就更新那个点的值。这种做法含有记忆化搜索的思想。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
char d[31][51];
char r[] = {'D', 'U', 'L', 'R'};
int nx[] = {1, -1, 0, 0};
int ny[] = {0, 0, -1, 1};
int minv = 0x3f3f3f3f;
string res = "";
bool st[31][51];
int mastep[31][51];
void dfs(int len, int x, int y, string ans)
{
    if (x == 30 && y == 50)
    {
        if (len == minv)
        {
            res = min(res, ans);
        }
        if (len < minv)
        {
            minv = len;
            res = ans;
        }
        return;
    }
    for (int i = 0; i < 4; i ++)
    {
        int xx = x + nx[i], yy = y + ny[i];
        if (xx < 1 || xx > 30 || yy < 1 || yy > 50 || st[xx][yy] || d[xx][yy] == '1') continue;
        if (len + 1 > mastep[xx][yy]) continue;
        if (len >= minv) continue;
        st[xx][yy] = true;
        mastep[xx][yy] = len + 1;
        dfs(len + 1, xx, yy, ans + r[i]);
        st[xx][yy] = false;
    }
}
int main()
{
    memset(mastep, 0x3f, sizeof mastep);
    for (int i = 1; i <= 30; i ++)
        for (int j = 1; j <= 50; j ++)
            cin >> d[i][j];
    dfs(0, 1, 1, "");
    cout << res << endl;
    return 0;
}

答案：

#include <iostream>
using namespace std;
int main()
{
    cout << "DDDDRRURRRRRRDRRRRDDDLDDRDDDDDDDDDDDDRDDRRRURRUURRDDDDRDRRRRRRDRRURRDDDRRRRUURUUUUUUULULLUUUURRRRUULLLUUUULLUUULUURRURRURURRRDDRRRRRDDRRDDLLLDDRRDDRDDLDDDLLDDLLLDLDDDLDDRRRRRRRRRDDDDDDRR" << endl;
}

为了巩固我的基础，准备来做一个博客系统来沉淀一下。
前端 Next.js , tailwindcss
ui figma
后端 Hertz
数据库 mysql

今日进度：
前端立项，后端立项，ui开始设计，xmind设计需求。一切都在朝好的方向发展！

Cobra 是go语言中用于创建 CLI 应用程序的库。
本身提供了一个快速创建 cli 应用的脚手架 cobra-cli

安装：

cobra:

go get -u github.com/spf13/cobra@latest

cobra-cli：

go install github.com/spf13/cobra-cli@latest

快速创建应用：

现在假设要创建一个名为test的cli程序，你可以使用一下步骤来创建

1. 初始化新的go模块：

go mod init test

2. 使用cobra-cli来快速创建应用模板

cobra-cli init

2.1 cobra-cli init 提供三个可选标志

--author ：

cobra-cli init --author "Steve Francia [email protected]"

--license ：

cobra-cli init --license apache

--viper ：

cobra-cli init --viper

使用 --viper 标志自动设置 viper
Viper 是 Cobra 的伴侣，旨在轻松处理环境变量和配置文件，并将它们无缝连接到应用程序标志。

3. 向项目添加命令

这个部分使用cobra-cli的add命令，例如：

cobra-cli add serve
cobra-cli add config
cobra-cli add create -p 'configCmd'

您会注意到，此最终命令具有 -p 标志。这用于将父命令分配给新添加的命令。在这种情况下，我们想将 “create” 命令分配给 “config” 命令。如果未指定，则所有命令的默认父级为 rootCmd。
默认情况下，cobra-cli 会将 Cmd 附加到提供的名称，并将此名称用作内部变量名称。指定父级时，请确保与代码中使用的变量名称匹配。
注意：命令名称使用 camelCase（而不是 snake_case/kebab-case）。否则，您将遇到错误。例如，cobra-cli add add-user 不正确，但 cobra-cli add addUser 有效。

最终在运行完这三个命令之后会在 cmd 文件夹中看到对应命令的go文件。这时可以参考官方文档来进行编写对应的代码。

参考：

1. cobra github
2.  Cobra 生成器README
3. Cobra 用户指南

最近在去听某个做软件开发的团队介绍平时的工作流程的时候，有讲到一个做思维导图的软件，是叫做xmind。我打算最近学习使用这个软件。看起来，感觉做的很漂亮，这个软件。

url: https://ybt.ssoier.cn/problem_show.php?pid=1638

tag:
裴蜀定理，拓展欧几里得算法，数论

思路：
根据题意可以得出，y - x = b d mod n ⇒ b d - a n = y - x。所以可以先求出n与d的最大公约数，如果y - x 不能整除，说明不能到达，如果可以整除再求最小的b。用拓展欧几里得算法可以求出 x n + y d = (n,d) 的一组解，然后令该式两边同乘 （y - x）/ （n，d）可以将该式变为b d - a * n = y - x。最后求最小的d就是让其取模n / gcd的正余数。
代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL exgcd(LL a, LL b, LL &x, LL &y)
{
    if (!b)
    {
        x = 1, y = 0;
        return a;
    }
    LL d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
int main()
{
    int T;
    cin >> T;
    while (T --)
    {
        LL n, d, x, y, a, b;
        scanf("%lld%lld%lld%lld", &n, &d, &x, &y);
        LL gcd = exgcd(n, d, a, b);
        if ((y - x) % gcd) cout << "Impossible\n";
        else
        {
            b *= (y - x) / gcd;
            n /= gcd;
            printf("%lld\n", (b % n + n) % n);
        }
    }
    return 0;
}