头像

ghy




离线:6分钟前



ghy
6小时前
/**
 * 最大异或对是在已知数中选择,是没有自主操控权的,
 * 但是这里k是在范围内任选的,是有很大的操控权力的,可以去拼凑最大值
 */
// const int N = 3000000;

// class Solution {
// public:
//     int idx;
//     vector<vector<int>> son = vector<vector<int>>(30, vector<int>(3, 0));

//     int query(int x)
//     {
//         int p = 0, res = 0;
//         for (int i = 20; i >= 0; -- i)
//         {
//             int t = (x >> i) & 1;
//             if (son[p][!t])
//             {
//                 res = (res << 1) + !t;
//                 p = son[p][!t];
//             }
//             else {
//                 res = (res << 1) + t;
//                 p = son[p][t];
//             }
//         }

//         return res;
//     }
//     void insert(int x)
//     {
//         int p = 0;
//         for (int i = 20; i >= 0; -- i)
//         {
//             int& t = son[p][x >> i & 1];
//             if (!t) t = ++ idx;
//             p = t;
//         }
//     }
//     vector<int> getMaximumXor(vector<int>& nums, int maximumBit) {
//         int n = nums.size();
//         int range = 1 << maximumBit;
//         vector<int> res;
//         vector<int> b = vector<int>(n);

//         // 异或前缀和
//         b[0] = nums[0];
//         for (int i = 1; i < n; ++ i)
//             b[i] = b[i - 1] ^ nums[i];

//         // trie树
//         for (int i = 0; i < range; ++ i) insert(i);

//         for (int i = n; i >= 0; -- i)
//             res.push_back(query(b[i]));

//         return res;
//     }
// };
class Solution {
public:
    vector<int> getMaximumXor(vector<int>& nums, int m) {
        vector<int> res;

        for (int i = 0, xorSum = 0; i < nums.size(); ++ i) {
            xorSum ^= nums[i];
            res.push_back(xorSum ^ ((1 << m) - 1));
        }
        reverse(res.begin(), res.end());

        return res;
    }
};


活动打卡代码 AcWing 178. 第K短路

ghy
22小时前
/**
 * 找到第k短路只能通过寻找所有路径,从中找到第k短的路径
 * 如果路径长度均相等,那么寻找所有路径可以采用bfs,对于某个点而言,所有路径就是拓展它可以拓展出的所有点
 * 但是在本题中,路径长度并非均相等,所以
 * 在bfs过程中我们保证,根据dijkstra的思想,
 * 
 * BFS是A*在估价函数取0时的一种情况,所以A*能解决的BFS一定可以解决(这里说的解决是指小样例可得到正确答案,大数据会超时)
 * A*只是在BFS的基础上,将状态选择的依据变得更全面一些以减少无关状态的搜索
 * 所以首先应考虑用一般BFS应该如何做
 * 
 * 如果是不知道题目标签的条件下,未必直接想到BFS,可能首先想到的DFS,想着找到距离前k的所有路径长度,但这是做不到的
 * 因为DFS可能搜到了10条指定路径但其中就是没有第1小的路径,可是此时要求的就是第1小的路径,自然就做不到了
 * 
 * 从BFS入手,因为目前为止我们会的就是求第1短路,第k短路或许是从第1短路拓展出去的
 * 
 * 在最短路问题中,我们每次都是让被更新了点进入队列,当然体现在dijkstra中因为每次都会选择用所有点去
 * BFS感觉上是让所有点都进入队列,但因为它保证距离一样是增加的,所以只要遍历到的点就是被更新了的,所以感觉上是让所有点都入队了
 * 
 * 从所有路径中找到第k小的路径
 * 采用优先队列,可以保证先出队的点一定距离更小
 * 根据dijkstra的思想,可以保证出队时的距离一定最小距离
 * 以上两点就可以保证第k次出队的距离就是第k小的距离
 * 对于a点估值函数值就选择从终点到a点的最短距离,因为在从起点经过a点到达终点的路径中,从a点到终点的路径长度一定>=从a点到终点的最短距离
 * 即估值函数值满足<=真实值
 * 从优先队列中取出某个点a,遍历它的所有相邻的点,这样就相当于考虑着所有路径(BFS)
 * 优先队列中的各点按照从起点到该点+该点到终点的估计值进行排序(A*)
 * 终点第k次出队的值即为第k短路(Dijkstra)
 * 这道题的难点在于将一般BFS,A*,Dijkstra结合在一起,但每一部分都不是完整的,只是利用到了他们各自的思想
 * 而这三者之间又存在着紧密的联系,所以感觉有些混乱
 * 
 * 假如说bfs是采用堆来实现的,而且我们在对一个点拓展状态时,对于它周围的点,不考虑他们是否被更新过了
 * 全部都放进堆中,这样,对于一个点b而言,第1次出队时是起点到b的第1短路径,第2次出队时是起点到b点的第2短路径,第k次出队就是起点到b点的第k短路径
 * 这为什么是正确的?
 * 首先说明一点,当第2短的路径在堆中出现时,第1短的路径一定在堆中。
 * 这是因为每次搜索都会将所有可达的点放进堆中,假设此时采用的只是一般bfs的搜索策略,第1短的路径一定位于第2短的路径之前出现
 * 所以如果第2短的路径出现了,那么第1短的路径一定也出现了。
 * 此时堆中的状态是这样的,b点的第1短路和第2短路都处在堆中,其它一些点的距离也处在堆中。此时出队的可能是其它点,
 * 但可以保证b的第1短路一定在第2短路之前出队,所以仅对b而言,第1次出队就代表第1短路,第2次出队就代表第2短路,以此类推,第k次出队就是第k短路
 * 
 * 而A*只是对上面一般bfs搜索策略的一种优化,并没有改变整体的逻辑
 */
/** 先按照一般bfs搜索策略的思路写一下,以便更好地理解题目
 * 正确结果就是TLE
 */
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>

using namespace std;

typedef pair<int, int> PII;

// 点数的平方 > 边数,所以采用邻接表建图
const int N = 1010, M = 1e5 + 10;

int n, m;
int S, T, K;
int head[N], e[M], ne[M],w[M], idx;
int st[N]; // 记录某点第几次出队

void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = head[a];
    w[idx] = c;
    head[a] = idx ++;
}
int bfs()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, S});

    while (heap.size())
    {
        PII t = heap.top(); heap.pop();
        int dis = t.first, ver = t.second;

        ++ st[ver];
        if (st[T] == K) return dis;

        for (int i = head[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            // 为了寻找所有路径,不是仅在距离可以被更新时才放入队列
            heap.push({dis + w[i], j});
        }
    }
    return -1;
}
int main()
{
    cin >> n >> m;

    memset(head, -1, sizeof head);
    for (int i = 0; i < m; ++ i) 
    {
        int a, b , c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    cin >> S >> T >> K;
    /**
     * 当起点和终点相同时,第1短路径距离是0,即路径中没有边
     * 但是题目中要求路径中至少要有一条边,所以当起点和终点相同时,要求的第k短路径实际上是第k+1短路径
     * 因为合法的第1短路径按照算法计算应该是第2短路径,所以假设我们要求的就是第1短路径,K应该为2而非1,自然要求第k短路径时,K应该等于k+1而非k
     */
    if (S == T) ++ K;

    cout << bfs() << endl;

    return 0;
}
/**
 * 超时原因在于状态数过多
 * 下面我们考虑使用A*进行优化
 * A*只是在状态数量过多时,一般BFS会超时,可以考虑的一种优化方法
 * 并不应该成为一种新的解题思路
 * 所以正确的思路应该是首先考虑一般BFS实现,当发现一般BFS会超时时,考虑采用A*进行优化
 * A*就是改变了一般BFS的搜索顺序,优先搜索距离答案最近的状态,而非无脑搜索
 * 想要加快搜索速度,就是要尽快搜索到终点,这样才能尽快得到终点的1到k短路,
 * 所以自然就是优先搜索距离终点更近的点,所以我们的搜索顺序应当按照距离终点距离预估值从小到大来进行
 * 我会想这么一种情况,a点的预估值<b点的预估值,但a点的真实值>b点的真实值,这样的假设并没有影响预估值<=真实值的要求
 * 但是我想的是优先搜索a点,假设K值较小,还没有轮到b点找到终点就return了怎么办?
 * 这样想的问题在于优先搜索a点,找到了终点,此时堆中同时存在b点和终点,除非终点的dis<b点,否则一定优先选择b点而非终点,“还没有轮到b点”就有问题
 * 如果终点的dis< b点,那从b点到终点的路径也应该处在当前这个终点路径之,没有轮到b点并没有什么问题
 * 预估值总让我感觉会无法得到正确答案,但实际又是正确的
 * 
 * 从某点到终点的真实距离显然是>=从终点到该点的最短距离的,所以预估函数取从终点到该点的最短距离即可,即需要先从终点着跑一遍dijkstra求一下终点到各点的最短距离
 */
#include <iostream>
#include <algorithm>
#include <queue>
#include <cstring>
#include <cstdio>

using namespace std;

typedef pair<int, int> PII;
typedef pair<int, pair<int, int>> PIII;

const int N = 1010, M = 2e5 + 10;

int n, m;
int S, T, K;
int h[N], rh[N], e[M], ne[M], w[M], idx;
int st[N], dis[N];

// 堆优化版dijkstra
void dijkstra()
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    memset(dis, 0x3f, sizeof dis);

    dis[T] = 0;
    heap.push({dis[T], T});

    while (heap.size())
    {
        PII t = heap.top(); heap.pop();
        int distance = t.first, ver = t.second;

        if (st[ver]) continue;
        st[ver] = 1;

        for (int i = rh[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (distance + w[i] < dis[j])
            {
                dis[j] = distance + w[i];
                heap.push({dis[j], j});
            }
        }
    }
}
int a_star()
{
    memset(st, 0, sizeof st);
    priority_queue<PIII, vector<PIII>, greater<PIII>> heap;

    heap.push({dis[S], {0, S}});

    while (heap.size())
    {
        PIII t = heap.top(); heap.pop();
        int ver = t.second.second, distance = t.second.first;

        ++ st[ver];
        if (st[T] == K) return distance; // 如果这里的堆使用PII,第一维度存放起点到该点真实值+估计值,第二维度存放点的编号,就无法获取距离起点的距离了

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (st[j] < K) // 不加这个判断就会超时
            /**
             * 对于b点而言,如果从它的第k+1短路到达终点,那么终点的距离一定>从它的第k短路到达终点所获得的终点的距离
             * 从第k短路到达终点所获得的终点距离一定>第k-1短路到达终点所获得的终点距离,
             * 所以b的第k+1短路是一定没有用的,假设就是从b点到达终点,那么b的第1短路获得终点的第1短路,第2短路获得终点的第2短路,第k短路获得终点的第k短路
             * b的第k+1短路一定不会派上用场,所以说如果此时ver已经出队k次,即获得了第k短路的距离了,就没必要再取获取第k+1短路的距离了
             */
                heap.push({distance + w[i] + dis[j], {distance + w[i], j}});
        }
    }

    return -1;
}
void add(int *h, int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = h[a];
    w[idx] = c;
    h[a] = idx ++;
}
int main()
{
    cin >> n >> m;

    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    for (int i = 0; i < m; ++ i)
    {
        int a, b , c;
        cin >> a >> b >> c;
        add(h, a, b, c); 
        add(rh, b, a, c);
    }

    cin >> S >> T >> K;
    if (S == T) ++ K;

    dijkstra();

    cout << a_star() << endl;

    return 0;
}


活动打卡代码 AcWing 179. 八数码

ghy
7天前
/**
 * A*算法适用于搜索空间非常庞大的bfs问题
 * 
 * 八数码问题一定有解的充要条件为将二维数组按照行优先的顺序从左到右依次读取获得的序列的逆序对数量一定为偶数
 * 必要性证明(问题有解说明逆序对数量一定为偶数):因为行内移动不会改变逆序对,行间移动对于逆序对数量的改变为偶数,所以任何变换都不会改变
 * 序列逆序对数量的奇偶,目标序列的逆序对数量为0,即偶数,所以只有当初始状态序列的逆序对数量为偶数时才有可能化为目标状态
 * 充分性证明(初始逆序对数量为偶数则问题一定有解):较难证明
 */
// 为了便于理解正解,先用以前的方法做一遍,虽然明知道会超时(啊,居然过了,这是没想到的)
// #include <iostream>
// #include <algorithm>
// #include <queue>
// #include <unordered_map>

// using namespace std;

// string bfs(string start)
// {
//     string end = "12345678x";
//     queue<string> q;
//     unordered_map<string, int> dis;
//     unordered_map<string, pair<string, char>> prev;
//     char op[] = {'u', 'r', 'd', 'l'};
//     int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

//     q.push(start);
//     dis[start] = 0;

//     while (q.size())
//     {
//         string t = q.front(); q.pop();
//         int k = t.find('x');
//         int x = k / 3, y = k % 3;

//         if (t == end)
//         {
//             string res("");
//             while (end != start)
//             {
//                 res += prev[end].second;
//                 end = prev[end].first;
//             }
//             reverse(res.begin(), res.end());
//             return res;
//         }
//         for (int i = 0; i < 4; ++ i)
//         {
//             int a = x + dx[i], b = y + dy[i];
//             string str(t);
//             swap(str[k], str[a * 3 + b]);
//             string state =str;

//             if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;
//             if (dis.count(state)) continue;

//             dis[state] = dis[t] + 1;
//             prev[state] = {t, op[i]};
//             q.push(state);
//         }
//     }

//     return "unsolvable";
// }
// int main()
// {
//     string start("");

//     char c;
//     while (cin >> c) start += c;

//     string t = bfs(start);

//     cout << t << endl;

//     return 0;
// }

/**
 * 一般bfs的问题是每次我们找的都是从当前状态来看最好的
 * 但是当前状态最优的不代表之后的状态也是最优
 * 假设把整个搜索过程看为两段,我们选择的是前半段最优的,但后半段的情况到目前为止还是未知的
 * 所以很可能就会遇到这种情况:5 + 10 与 9 + 2,虽然从前半段看前者更优,但从全局来看后者更优
 * 而一般bfs我们选择的一定是前者(当前状态最优),所以A*算法就是想办法解决这样一种情况
 * 我们可以预估一下最终结果,每次选择预估最终结果最小的去拓展,相当于去考虑全局的情况而非当前状态
 * 反映在本题中,如果采用一般bfs,我们选择的状态离目标状态可能很远,
 * 但是采用A*算法,我们会采用一个估价函数,计算某个状态的预估结果,按照这个结果的大小决定搜索的优先级显然会优先搜索距离目标状态最近的点,搜索的状态数量就会减少
 * 
 * 所以问题在于如何确定估价函数,若想得到正确答案,估价函数得到的预估值是有条件的:预估值<=真实值
 * 证明:考虑若预估值>真实值会怎么样呢?
 * 如果我们一直优先搜索的都是距离目标状态距离最近的点,那么当目标状态第一次出现时的距离就是最短距离
 * 但是在假设情况下,我们优先搜索到的状态有可能是真实值较大的状态,那么当目标状态第一次出现时得到的距离就未必是最短距离
 * 这样在
 * 在一般bfs问题中,我们采用的是队列,显然采用优先队列(小根堆)也是一样的,不过由于一般bfs问题中,
 * 
 * 从起点到当前点的距离 + 从当前点到终点的预估距离
 * A*可以处理负权边,不能有负权回路
 * 无论是bfs还是A*在思想上和dijkstra都有关联性
 * 一般bfs只能解决边权唯一的情况,使用双端队列可以解决边权有两种值的情况
 * dijkstra可以解决边权非负的情况
 * 而A*可以解决任意边权的情况
 * 原因在于:我们首先考虑为什么dijkstra不能作用与含有负边权的情况?因为dijkstra采用的贪心的思想,当前选择最小的则最终一定得到最小的
 * 即局部最优解即为全局最优解,但是当含有负边权时,这条显然就不再成立了,因为当前最小不代表最终最小,例如4+1 > 5 + (-2),虽然4比5小,
 * 但负边权会破环这种关系,贪心也就不再成立了
 * dijkstra实际上考虑的也只是全部路径中的一部分,但A*考虑的是全局情况,它并不会仅参考4和5,它会参考4+1和5+(-2),所以负权边
 * 并不会影响A*,所以A*可以处理负边权。对于负权回路,只有能判断当前路径中包含多少点的spfa能够判断是否存在负权回路并及时处理,
 * 其它算法并不能处理
 * 
 * A*算法只有在有解的条件下是优化的,无解时还是会搜索完所有状态,这样效率比bfs就差了,因为bfs使用队列,而A*使用优先队列
 * 前者是o(1)的但后者是o(logn)的,所以最好是在确保有解的条件下使用A*算法
 * 
 * 如何证明在以起点到当前状态距离+当前状态到终点的预估距离为根据确定搜索的优先顺序时,当终点状态第一次出队时得到的一定是最优解
 * 反证法:假设终点出队时得到的不是最优解,那么可以得到一个结论是此时队列中存在一个比终点状态值更小的值,说明此时出队的就不该是终点,和假设矛盾了
 * 
 * 一般bfs,双端队列bfs,A*和dijkstra,只有一般bfs可以保证随着搜索的进行,搜索到点的距离是严格增加的,其余均无法保证,所以只有一般bfs每个点仅需入队一次,其余都有可能是多次,因为随着所有的进行,点的距离是有可能减小的,一旦减小就需要重新入队
 * 
 * 估价函数值会影响搜索的顺序,所以当估价函数大于真实值时,可能会使得我们不会从最优路径走
 * 得到的答案也不是最优的
 * 
 * 当预估值大于真实值时,不对的原因是,考虑我们将真实值为L点的预估值定为L+1000,那么就不会有拨乱反正的过程了,从错误路径走得到的就是错误的结果,虽然预估值不会对答案没有直接影响,但是它会通过影响搜索顺序影响最终答案
 */
#include <iostream>
#include <algorithm>
#include <queue>
#include <unordered_map>

using namespace std;

int f(string state) // 估价函数-获取状态state的估价值
{
    int res = 0;
    for (int i = 0; i < state.size(); ++ i)
        if (state[i] != 'x')
        {
            int t = state[i] - '1';
            res += abs(i / 3 - t / 3) + abs(i % 3 - t % 3);        
        }
    return res;
}
string bfs(string start)
{
    string end = "12345678x";
    char op[] = {'u', 'r', 'd', 'l'};
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    unordered_map<string, int> dis;
    unordered_map<string, pair<string, char>> prev;
    priority_queue<pair<int, string>, vector<pair<int, string>>, greater<pair<int, string>>> heap;

    dis[start] = 0;
    heap.push({f(start), start});

    while (heap.size())
    {
        auto t = heap.top(); heap.pop();
        string state = t.second;
        int k = state.find('x');
        int x = k / 3, y = k % 3;

        if (state == end)  break;
        for (int i = 0; i < 4; ++ i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= 3 || b < 0 || b >= 3) continue;

            string tmp(state);
            swap(tmp[k], tmp[a * 3 + b]);

            if (!dis.count(tmp) || dis[tmp] > dis[state] + 1) // 此前除了dijkstra都是直接更新dis[tmp],不需要判断,而dijkstra实现时用的是数组都进行了初始化,这里并没有初始化,虽然默认值是0但从严谨性的角度来说还是要判断是否是不存在的情况的
            {
                dis[tmp] = dis[state] + 1;
                prev[tmp] = {state, op[i]};
                heap.push({dis[tmp] + f(tmp), tmp}); // 注意我们存放的应该是起点到该状态距离+该状态到终点的预估距离,即考虑的是最终答案,按照最终答案的大小安排的搜索顺序才是最优的
            }
        }
    }

    string res("");
    while (end != start)
    {
        res += prev[end].second;
        end = prev[end].first;
    }
    reverse(res.begin(), res.end()); // 记得翻转
    return res;
}
int main()
{
    char c;
    string start, seq;

    while (cin >> c)
    {
        start += c;
        if (c != 'x') seq += c;
    }

    int cnt = 0;
    for (int i = 0; i < seq.size(); ++ i)
        for (int j = i + 1; j < seq.size(); ++ j)
            if (seq[i] > seq[j]) ++ cnt;

    if (cnt & 1) cout << "unsolvable" << endl;
    else cout << bfs(start) << endl;

    return 0;
}


活动打卡代码 AcWing 190. 字串变换

ghy
9天前
/**
 * 搜索的思路并不难想到,每一个状态都是一个字符串
 * 向外拓展就是使用每一个规则进行替换
 * 难点在于如何使用每一个规则
 * 
 * 看完讲解发现是自己想复杂了,规则的使用就是字符串的一般处理,不会涉及到什么复杂的字符串算法,觉得复杂完全是畏惧心里,就像此前面对树和图的问题一样
 * 
 * 本题的核心考点显然不是变换规则如何使用。由于状态数量过多,一般的bfs会超时,应当从起点和终点同时向中间搜索,
 * 如果是单向搜索,状态数量的增加并不是线性级别的,而是指数级别的,单向搜索与从两端向中间搜索的差别类似a^b与2*a^(b/2)的差别
 * 会大幅度减少搜索的状态数量,为了更加清晰的理解,首先实现一下单向bfs
 * 
 * 写完代码真的发现,感觉字符串问题较难不是我的错觉,是真的和其它问题不一样,在一些问题上很容易就想错或想不明白
 */

// 单向bfs
// #include <iostream>
// #include <algorithm>
// #include <queue>
// #include <unordered_map>

// using namespace std;

// const int N = 10;

// int n;
// string A, B;
// string a[N], b[N];
// queue<string> q;
// unordered_map<string, int> dis;

// /**
//  * 第一次写遇到一个问题是在用a替换为b时只替换了第一个a就直接返回了
//  * 写之前确实想到了这个问题,如果有多个匹配的a怎么办
//  * 实际是当前只替换1个,放进队列后再遇到这个自然就会继续替换,替换1个,2个,。。。的情况都可以搜索到
//  * 但是如果有多个位置匹配,虽然说只替换一个,但是要将替换每一个位置的情况全部放进队列,而非第一个匹配的位置
//  */
// void extend(string t, string a, string b) // 把t中a的部分换为b
// {
//     for (int i = 0; i < t.size(); ++ i)
//         if (t.substr(i, a.size()) == a)
//         {
//             string ex = t.substr(0, i) + b + t.substr(i + a.size());

//             if (dis.count(ex)) continue;

//             q.push(ex);
//             dis[ex] = dis[t] + 1;
//         }
// }
// int bfs()
// {
//     q.push(A);
//     dis[A] = 0;

//     while (q.size())
//     {
//         string t = q.front();
//         q.pop();

//         if (t == B) return dis[t];

//         for (int i = 0; i < n; ++ i)
//             extend(t, a[i], b[i]); 
//     }

//     return 11;
// }
// int main()
// {
//     cin >> A >> B;

//     while (cin >> a[n] >> b[n]) ++ n;

//     int t = bfs();

//     if (t > 10) cout << "NO ANSWER!" << endl;
//     else cout << t << endl;

//     return 0;
// }

/**
 * 双向bfs作为bfs的优化
 * 主要应用于最小步数模型中,即待搜索状态数极大的问题中
 * 棋盘中的路径问题不需要使用双向bfs是因为格点数目不会很大,搜索耗时较少
 * 
 * 双向bfs就是从起点和终点同时向中间搜索,从数学角度来看能够大幅度减少搜索的状态数量
 * 每次从元素数量较少的队列中取元素
 */
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstring>
#include <queue>
#include <unordered_map>

using namespace std;

const int N = 10;

int n;
string A, B;
string a[N], b[N];
queue<string> qa, qb;
unordered_map<string, int> da, db;

/**
 * 考虑q队列,里面元素的距离为da,另一队列中元素距离为db,将其中的a替换为b
 * 这里必须要加上da,db,否则我们不知道q队列的元素t的距离到底是da[t]还是db[t]
 */
int extend(queue<string> &q, unordered_map<string, int> &da, unordered_map<string, int> &db, string a[], string b[])
{
    // 我们要做的是将当前q中的元素全部拓展一遍,但是这样写会将拓展后的点也会被遍历
    // while (q.size())
    for (int k = 0, qs = q.size(); k < qs; ++ k)
    {
        string t = q.front();
        q.pop();

        for (int i = 0; i < t.size(); ++ i)
            for (int j = 0; j < n; ++ j)
                if (t.substr(i, a[j].size()) == a[j])
                {
                    string state = t.substr(0, i) + b[j] + t.substr(i + a[j].size());

                    if (da.count(state)) continue;
                    if (db.count(state)) return da[t] + 1 + db[state] ; // 已经找到交点就可以返回距离了, da[t] + 1就是da[state],因为此时da[state]还没有更新所以用da[t]

                    da[state] = da[t] + 1;
                    q.push(state);
                }
    }

    return 11; // q在拓展时并没有找到交点
}
int bfs()
{
    qa.push(A); da[A] = 0;
    qb.push(B); db[B] = 0;

    /**
     * 有解的条件是从起点向终点走和从终点向起点走应该能够走到同一个状态
     * 如果某个方向已经走完了还没有相遇就说明无解
     * 上面这个结论为什么是正确的?
     * 为了叙述的方便,我们定义从起点向终点走为方向a,从终点向起点走为方向b,
     * 我考虑一种情况为若b已经把所有情况都搜索完了,a还没有搜索完,此时还没遇到交点(交点就是a和b都走过的某个状态,显然起点和终点都算是交点),会不会可能交点在b中,但是a还没有走到交点
     * 这种想法是错误的,原因在于如果问题是有解的,那么单从b方向而言,最终一定是可以到达起点的
     * 就算是a方向上完全没有动,单从b方向也一定是可以走到起点的,这就变为了单向bfs
     * 而b的所有情况都搜索完成后并没有找到交点(这其中可是包含起点的),说明起点与终点之间是不存在通路的,即无解
     * 
     * 所以bfs的条件是两个队列均不为空,在这期间如果找到了答案说明有解,某个队列已经空了还没找到答案说明无解
     */
    while (qa.size() && qb.size())
    {
        int t;
        if (qa.size() <= qb.size()) t = extend(qa, da, db, a, b); // 对于qa 将a替换为b
        else t = extend(qb, db, da, b, a);

        if (t <= 10) return t;
    }

    return 11;
}
int main()
{
    cin >> A >> B;

    while (cin >> a[n] >> b[n]) ++ n;

    int t = bfs();

    if (t > 10) cout << "NO ANSWER!" << endl;
    else cout << t << endl;

    return 0;
}


活动打卡代码 AcWing 175. 电路维修

ghy
11天前
/**
 * 这两个方向应该用某种数学方式表示,直接用这样的符号没法做题
 * bfs的方式有点想不懂
 * 
 * 正解是把所有对角线都看为是路径,有线连着的路径长度为0,没有线连着的路径长度为1,这里说的路径长度实际指的是转动标准件的方向的消耗
 * 有线连着说明不需要转动,消耗为0,没有线连着说明需要转动,所以消耗为1
 * 所以问题转变为了在一个路径长度为0或1的图中求某两点之间的最短距离
 * 
 * 分析到目前为止,感觉这道题最难的在于问题建模,将一个翻转的动作转变为了路径问题
 * 在此之前是看不到bfs的影子的
 * 
 * 无解的情况也很神奇,假设坐标从(0,0)开始,能走到的点一定是横纵坐标相加为偶数的点
 * 
 * 一般的bfs只能处理路径长度均相等的情况,但在本问题中同时存在长度为0和1的路径,一般方法是无法解决的
 * 本质上为单源最短路问题,所以可以使用dijkstra来做
 * std使用的是双端队列bfs
 */

/**
 * dijkstra,不确定能不能过
 * 第一次写大意了,直接用邻接矩阵写,忽视了点的数量过多,用数组下标是放不下的,需要用邻接表实现
 * 但是代码是没有问题的,只是无法满足数据要求
 */
// #include <iostream>
// #include <algorithm>
// #include <cstdio>
// #include <cstring>

// using namespace std;

// const int N = 510;

// int t, n, m;
// int g[N][N];
// int dis[N * N];
// bool st[N * N];

// void dijkstra(int u)
// {
//     memset(st, 0, sizeof st);
//     memset(dis, 0x3f, sizeof dis);
//     dis[u] = 0;

//     for (int i = 0; i < (n + 1) * (m + 1); ++ i)
//     {
//         int t = -1;
//         for (int j = 0; j < (n + 1) * (m + 1); ++ j)
//             if (!st[j] && (t == -1 || dis[j] < dis[t]))
//                 t = j;

//         st[t] = true;

//         for (int j = 0; j < (n + 1) * (m + 1); ++ j)
//             dis[j] = min(dis[j], dis[t] + g[t][j]);
//     }
// }
// int main()
// {
//     cin >> t;
//     while (t --)
//     {
//         memset(g, 0x3f, sizeof g);

//         cin >> n >> m;
//         for (int i = 0; i < n; ++ i)
//             for (int j = 0; j < m; ++ j)
//             {
//                 char path;
//                 int a = i * (m + 1) + j, b = a + m + 2;
//                 int c = a + 1, d = c + m;

//                 cin >> path;
//                 if (path == '\\') 
//                 {
//                     g[a][b] = g[b][a] = 0;
//                     g[c][d] = g[d][c] = 1;
//                 }
//                 else 
//                 {
//                     g[a][b] = g[b][a] = 1;
//                     g[c][d] = g[d][c] = 0;                    
//                 }
//             }

//         dijkstra(0);

//         int res = dis[(n + 1) * (m + 1) - 1];
//         if (res == 0x3f3f3f3f) cout << "NO SOLUTION" << endl;
//         else cout << res << endl;
//     }

//     return 0;
// }

/**
 * dijkstra 邻接表实现
 * 不会segment error,但是超时了,原因在于点的数量过多,而dijkstar需要遍历所有点,所以会超时
 */
// #include <iostream>
// #include <algorithm>
// #include <cstdio>
// #include <cstring>

// using namespace std;

// const int N = 1e5 + 10;

// int t, n, m;
// int dis[N];
// bool st[N];
// int head[N], e[N], ne[N], w[N], idx;

// void insert(int a, int b, int k)
// {
//     w[idx] = k;
//     e[idx] = b;
//     ne[idx] = head[a];
//     head[a] = idx ++;
// }
// void dijkstra(int u)
// {
//     memset(st, 0, sizeof st);
//     memset(dis, 0x3f, sizeof dis);
//     dis[u] = 0;

//     // 每次距离更新后每个点都有可能已经被更新了,这是不确定的,所以必须考虑用所有点都进行一次松弛操作
//     // 不能想着仅用和u点相邻的点进行一次松弛操作就可以了,和它相邻的点松弛操作后可能会有其它和u点不相邻的店的距离被更新了
//     for (int i = 0; i < (n + 1) * (m + 1); ++ i)
//     {
//         int t = -1;
//         for (int j = 0; j < (n + 1) * (m + 1); ++ j)
//             if (!st[j] && (t == -1 || dis[j] < dis[t]))
//                 t = j;

//         st[t] = true;

//         for (int j = head[t]; j != -1; j = ne[j])
//         {
//             int p = e[j];
//             dis[p] = min(dis[p], dis[t] + w[j]);
//         }
//     }
// }
// int main()
// {
//     cin >> t;
//     while (t --)
//     {
//         memset(head, -1, sizeof head);

//         cin >> n >> m;
//         for (int i = 0; i < n; ++ i)
//             for (int j = 0; j < m; ++ j)
//             {
//                 char path;
//                 int a = i * (m + 1) + j, b = a + m + 2;
//                 int c = a + 1, d = c + m;

//                 cin >> path;
//                 if (path == '\\') 
//                 {
//                     insert(a, b, 0); insert(b, a, 0);
//                     insert(c, d, 1); insert(d, c, 1);
//                 }
//                 else 
//                 {
//                     insert(a, b, 1); insert(b, a, 1);
//                     insert(c, d, 0); insert(d, c, 0);
//                 }
//             }

//         dijkstra(0);

//         int res = dis[(n + 1) * (m + 1) - 1];
//         if (res == 0x3f3f3f3f) cout << "NO SOLUTION" << endl;
//         else cout << res << endl;
//     }

//     return 0;
// }

/**
 * 可用的优化就是使用小根堆优化寻找距离最小点的操作,能过但是很慢
 */
// #include <iostream>
// #include <algorithm>
// #include <cstdio>
// #include <cstring>
// #include <queue>

// using namespace std;

// typedef pair<int, int> PII;

// const int N = 1e6 + 10;

// int t, n, m;
// int dis[N];
// bool st[N];
// int head[N], e[N], ne[N], w[N], idx;

// void insert(int a, int b, int k)
// {
//     w[idx] = k;
//     e[idx] = b;
//     ne[idx] = head[a];
//     head[a] = idx ++;
// }
// void dijkstra(int u)
// {
//     memset(st, 0, sizeof st);
//     memset(dis, 0x3f, sizeof dis);
//     dis[u] = 0;
//     priority_queue<PII, vector<PII>, greater<PII>> heap;
//     heap.push({0, 0});

//     for (int i = 0; i < (n + 1) * (m + 1); ++ i)
//     {
//         PII p = heap.top();
//         int t = p.second;
//         heap.pop();

//         if (st[t]) continue;
//         st[t] = true;

//         for (int j = head[t]; j != -1; j = ne[j])
//         {
//             int p = e[j];
//             if (dis[t] + w[j] < dis[p])
//             {
//                 dis[p] = dis[t] + w[j];
//                 heap.push({dis[p], p});
//             }
//         }
//     }
// }
// int main()
// {
//     cin >> t;
//     while (t --)
//     {
//         memset(head, -1, sizeof head);

//         cin >> n >> m;
//         for (int i = 0; i < n; ++ i)
//             for (int j = 0; j < m; ++ j)
//             {
//                 char path;
//                 int a = i * (m + 1) + j, b = a + m + 2;
//                 int c = a + 1, d = c + m;

//                 cin >> path;
//                 if (path == '\\') 
//                 {
//                     insert(a, b, 0); insert(b, a, 0);
//                     insert(c, d, 1); insert(d, c, 1);
//                 }
//                 else 
//                 {
//                     insert(a, b, 1); insert(b, a, 1);
//                     insert(c, d, 0); insert(d, c, 0);
//                 }
//             }

//         dijkstra(0);

//         int res = dis[(n + 1) * (m + 1) - 1];
//         if (res == 0x3f3f3f3f) cout << "NO SOLUTION" << endl;
//         else cout << res << endl;
//     }

//     return 0;
// }

/**
 * bfs 和dijkstra算法的思想是一样的
 * 
 * 正解:双端队列广搜
 * 一般bfs所能解决的问题是所有路径长度均相等
 * 证明需要证明1.两段性 2.单调性
 * 所谓两段性是指序列中的元素能够分为两部分,x, x, x, x + 1, x + 1, x + 1
 * 上述序列即满足单调性
 * 
 * 在满足这两个性质之后为何能保证bfs是正确的?因为队列中的元素同时具备两段性和单调性,同时根据dijkstra算法,
 * 从队头拿出的元素就是“未确定最短路径的点中距离起点距离最小的点”,同时我们将从它拓展出的点放到队尾,由于bfs保证所有路径长度均相等,
 * 所以放到队尾的元素一定还能保证队列中的元素满足两段性和单调性,所以bfs算法是正确的
 * 
 * 但在本题中,如果我们仍采用一般bfs的策略,由于同时存在路径长度为0和1的点,所以从对头元素拓展出的点放到队尾后并不能保证序列仍具备
 * 两段性和单调性,所以得到的结果并不正确。
 * 但如果我们采用双端队列,将路径长度为0拓展出的点放到对头,路径长度为1拓展出的点放到队尾,两端性和单调性就能够满足了,算法自然也就正确了
 * 双端队列bfs解决的就是路径长度为0和1的图中的最短路
 * 
 * 本问题中某个点可能会被更新多次即可能会多次入队,一般bfs问题中一个点只可能会被更新一次即仅入队一次
 * 这是因为在一般bfs问题中,某个点第二次被拓展到时的距离一定 >= 第一次被拓展到的距离,假设第一次拓展到它的点为i,第二次为j
 * i的距离di一定是<=j的距离dj的,而一般问题中边的路径又都是相等的,我们设为d,那么di+d一定<=dj+d。所以第二次被拓展到时就没必要再放进队列了
 * 但在本问题中,既有又di<=dj,但是路径长度并不是全部均为d,第一次拓展距离为di+1,第二次拓展距离为dj+0,不能再保证第二次被拓展到的距离>=第一次被拓展到的距离
 * 所以这个点就需要入队两次,但是用这个点去更新时只需要一次(根据dijkstra算法可得),即使这个点入队多次,但是我们都选取距离最小的那次(体现在小根堆中就是选择堆顶元素,体现在双端队列中就是取对头元素)
 * 
 * 同小根堆优化版dijkstra相比到底哪里更节省时间了?
 * 根据我的理解,两者是一样的,都是每次选择距离起点最近的点,用该点去更新和它相邻点的距离,但是运行时间差距却很大
 * 两种算法每个点都是只会用于松弛操作一次(因为核心都是dijkstra的思想),只不过堆优化dijkstra使用的是小根堆,但std用的是双端队列
 * 这样来说,差别就在我写的dijkstra初始阶段需要遍历整个数组完成建图,这项工作还是很耗时的,但是这项工作已经没办法再优化了,建图必须要将
 * 图中的所有顶点都赋予一个编号,这就必须要遍历整个字符数组,但是bfs是不需要建图的,所以这项工作的时间也就节省掉了
 * 其次,小根堆和双端队列虽然取最小值都是O(1)的,但小根堆每插入一个元素都需要进行维护而双端队列则不需要
 * 其它原因我也没想出来
 * 
 * 最终分析下来,发现思想完全就是dijkstra了,从以往对bfs的理解是不能理解该算法流程的,但是如果从dijkstra的角度就很好理解
 * 
 * 照这么来说的话,dijkstra缺点就在于必须要建图,而花费时间最多的工作就是建图,而bfs是不需要的
 * 但由于条件并不满足一般bfs问题,所以需要使用双端队列使其满足两段性和单调性
 */
// 代码实现的难点在于如何快速判断某两点间的路径长度
#include <iostream>
#include <algorithm>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <deque>

using namespace std;

typedef pair<int, int> PII;

const int N = 510;

int n, m;
char g[N][N];
int dis[N][N];
bool st[N][N];

int bfs()
{
    deque<PII> q;
    char cs[] = "\\/\\/"; // 定义的是距离为0的标准方向,也可以定义为距离为1,下面代码对应变化即可
    int dx[] = {-1, -1, 1, 1}, dy[] = {-1, 1, 1, -1};
    int ix[] = {-1, -1, 0, 0}, iy[] = {-1, 0, 0, -1}; // 从格点推导到格子坐标

    memset(dis, 0x3f, sizeof dis);
    memset(st, 0, sizeof st);

    q.push_front({0, 0});
    dis[0][0] = 0;

    while (q.size())
    {
        PII t = q.front();
        q.pop_front();
        int x = t.first, y = t.second;

        // 根据dijkstra算法,每个点只需进行一次松弛操作
        if (st[x][y]) continue;
        st[x][y] = true;

        for (int i = 0; i < 4; ++ i) 
        {
            int a = x + dx[i], b = y + dy[i]; // 周围拓展到的点(a, b)的坐标
            if (a < 0 || a > n || b < 0 || b > m) continue;

            int ca = x + ix[i], cb = y + iy[i]; // 对应拓展方向的格子坐标
            /**
             * 点(x, y)到点(a, b)的距离为0还是1,这个就需要看从点(x, y)到点(a, b)的真实路径方向和假设距离为0或者距离为1的方向是否相等
             * 假设我们现在分析(x, y)距离左上角的点的距离
             * 我们需要能够根据当前点的坐标推导出左上角的格子的坐标,这样才能找到真实路径方向(从图中即可得出变换公式)
             * 当左上角的符号是'\'时说明路径长度为0,我们只需要用左上角格子的真实路径和'\'做个比较即可,相同为0不同为1。所以需要我们定义一个标准方向
             */
            int w = g[ca][cb] != cs[i]; // 当和标准方向不同是距离恰好为1
            int d = dis[x][y] + w; // 从(0, 0)到点(a, b)的距离

            if (d < dis[a][b])
            {
                dis[a][b] = d;

                if (!w) q.push_front({a, b});
                else q.push_back({a, b});
            }
        }
    }

    return dis[n][m]; // 终点可能多次进队,第一次进队时不一定就是最小距离。从dijkstra算法的角度来看当所有点都完成松弛操作后算法才结束。
}
int main()
{
    int T;
    cin >> T;

    while (T --)
    {
        cin >> n >> m;
        for (int i = 0; i < n; ++ i) cin >> g[i];

        int t = bfs();

        if (t == 0x3f3f3f3f) cout << "NO SOLUTION" << endl;
        else cout << t << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1107. 魔板

ghy
12天前
/**
 * 两个核心的思想:
 * 1. 每一个状态用字符串表示,需要使用哈希(unordered_map 或 康托展开和逆康托展开,这里为了方便我们采用unordered_map)
 * 2. 需要使用坐标变换将一维空间映射到二维空间中
 * 
 * 清楚这两个核心思想后,问题的难点就变为了如何进行坐标映射
 * A:字符串翻转
 * B:a[3]移动到a[0],a[4]移动到a[7]
 * c:a[1]->a[2], a[2]->a[5], a[5]->a[6], a[6]->a[1]
 * 
 * 由于本题只有两行,所以可以采用二维数组直接模拟二维空间,不再需要进行一维到二维的坐标映射
 */
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <unordered_map>

using namespace std;

typedef pair<char, string> PII;

const int N = 40500;

unordered_map<string, int> dis;
unordered_map<string, PII> path;
string q[N];
char stk[N];

int bfs(string end)
{
    string start = "12345678";
    int hh = 0, tt = -1;
    dis[start] = 0;
    q[++ tt] = start;

    while (tt >= hh)
    {
        string t = q[hh ++];
        if (t == end) return dis[t];

        string a(t);
        reverse(a.begin(), a.end());
        if (!dis.count(a)) 
        {
            dis[a] = dis[t] + 1;
            path[a].first = 'A', path[a].second = t;
            q[++ tt] = a;
        }

        string b(t);
        char u(b[3]), v(b[4]);
        for (int i = 3; i > 0; -- i) b[i] = b[i - 1];
        b[0] = u;
        for (int i = 4; i < 7; ++ i) b[i] = b[i + 1];
        b[7] = v;
        if (!dis.count(b))
        {
            dis[b] = dis[t] + 1;
            path[b].first = 'B', path[b].second = t;
            q[++ tt] = b;
        }


        string c(t);
        u = c[6];
        c[6] = c[5];
        c[5] = c[2];
        c[2] = c[1];
        c[1] = u;
        if (!dis.count(c))
        {
            dis[c] = dis[t] + 1;
            path[c].first = 'C', path[c].second = t;
            q[++ tt] = c;
        }
    }

    return -1;
}
int main()
{
    string end("");

    for (int i = 0; i < 8; ++ i) 
    {
        char c;
        cin >> c;
        end += c;
    }

    cout << bfs(end) << endl;

    int tt = -1;
    for (string s = end; s != "12345678"; s = path[s].second) stk[++ tt] = path[s].first;
    while (tt >= 0) cout << stk[tt --];

    return 0;
}


活动打卡代码 AcWing 173. 矩阵距离

ghy
12天前
/**
 * 每个位置距离最近的1的距离
 */
从每个待求位置开始bfs,超时
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
int g[N][N];
char ch[N][N];
PII q[M];
bool st[N][N];
int dis[N][N], step;

void bfs(int sx, int sy)
{
    int hh = 0, tt = -1;
    int dx[] = {-1, 0, 1, 0};
    int dy[] = {0, 1, 0, -1};

    memset(st, 0, sizeof st);
    st[sx][sy] = true;
    q[++ tt] = {sx, sy};
    step = 0;

    while (tt >= hh)
    {
        int size = tt - hh + 1;
        while (size --)
        {
            PII t = q[hh ++];
            int a = t.first, b = t.second;

            if (g[a][b]) 
            {
                dis[sx][sy] = step;
                return ;
            }
            for (int i = 0; i < 4; ++ i)
            {
                int x = a + dx[i], y = b + dy[i];
                if (x < 0 || x >= n || y < 0 || y >= m || st[x][y]) continue;

                st[x][y] = true;
                q[++ tt] = {x, y};
            }
        }
        ++ step;
    }
}
int main()
{
    cin >> n >> m;

    for (int i = 0; i < n; ++ i) cin >> ch[i];

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            g[i][j] = ch[i][j] - '0';

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            if (!g[i][j]) bfs(i, j);

    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < m; ++ j)
            cout << dis[i][j] << ' ';
        cout << endl;
    }

    return 0;       
}

/**
 * 从目标位置开始bfs
 * 正着不行就反着来
 * 多元最短路解法的证明可以通过引入一个虚拟原点,
 * 该原点距离所有起点的距离为0,多元最短路问题此时已经变为了一个单元最短路问题
 * 采用迪杰斯特拉算法即可得到答案,正确性也已经被证明过了
 */

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n, m;
char g[N][N];
int dis[N][N];
PII q[M];

void bfs()
{
    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
    int hh = 0, tt = -1;
    memset(dis, -1, sizeof dis);

    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
            if (g[i][j] == '1')
            {
                dis[i][j] = 0;
                q[++ tt] = {i, j};
            }

    while (tt >= hh)
    {
        PII t = q[hh ++];
        int a = t.first, b = t.second;

        for (int i = 0; i < 4; ++ i)
        {
            int x = a + dx[i], y = b + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || dis[x][y] != -1) continue;

            dis[x][y] = dis[a][b] + 1;
            q[++ tt] = {x, y};
        }
    }

}
int main()
{
    cin >> n >> m;
    for (int i = 0; i < n; ++ i) cin >> g[i];

    bfs();

    for (int i = 0; i < n; ++ i)
    {
        for (int j = 0; j < m; ++ j) cout << dis[i][j] << ' ';
        cout << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1100. 抓住那头牛

ghy
18天前
/**
 * 1. 不能保证之前走过的点再走一次时更差(地图问题中是可以保证这一点的) 错了,因为每步的操作时间代价均为1,先走到这个点一定比后走到这个点所用的时间更短,这也就是为什么在边的长度为1时可以用bfs确定最短路径
 * 2. 走到k的右边是否一定不会是最优解:不一定,先走到k的右边再往左走可能比直接向右走到目标更优
 * 
 * 只有-1可以向左走,+1和*2只能向右走
 * 所以<0的点是一定不会走的,因为从<0的点走到>=0的点只能通过+1,先-1再+1做的是无用功
 * 向右最多只会走到2e5,因为当k已经在左侧时,即当前位置处于k的右侧时,一定不会选择+1或*2了,最后一个可能*2的位置在1e5,所以最大需要2e5的空间
 */
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 2e5 + 10;

int n, k;
bool st[N];
int q[N], dis[N];

void bfs(int u)
{
    int hh = 0, tt = -1;
    st[u] = true;
    q[++ tt] = u;

    while (tt >= hh)
    {
        int t = q[hh ++];
        if (t == k) return ;

        int p = t - 1;
        if (p >= 0 && !st[p])
        {
            st[p] = true;
            q[++ tt] = p;
            dis[p] = dis[t] + 1;
        }

        p = t + 1;
        if (p < N && !st[p])
        {
            st[p] = true;
            q[++ tt] = p;
            dis[p] = dis[t] + 1;
        }

        p = t << 1;
        if (p < N && !st[p])
        {
            st[p] = true;
            q[++ tt] = p;
            dis[p] = dis[t] + 1;
        }
    }
}
int main()
{
    cin >> n >> k;

    bfs(n);
    cout << dis[k] << endl;

    return 0;
}


活动打卡代码 AcWing 188. 武士风度的牛

ghy
18天前
#include <iostream>
#include <algorithm>

using namespace std;

typedef pair<int, int> PII;

const int N = 160, M = N * N;

int n, m;
int sx, sy, ex, ey;
char ma[N][N];
bool st[N][N];
PII q[M];
int dis[N][N];

void bfs(int sx, int sy)
{
    int dx[] = {-2, -2, -1, 1, 2, 2, 1, -1};
    int dy[] = {-1, 1, 2, 2, 1, -1, -2, -2};

    int hh = 0, tt = -1;
    q[++ tt] = {sx, sy};
    st[sx][sy] = true;
    dis[sx][sy] = 0;

    while (tt >= hh)
    {
        PII t = q[hh ++];
        int xx = t.first, yy = t.second;

        for (int i = 0; i < 8; ++ i)
        {
            int x = xx + dx[i], y = yy + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= m || st[x][y] || ma[x][y] == '*') continue;

            q[++ tt] = {x, y};
            st[x][y] = true;
            dis[x][y] = dis[xx][yy] + 1;

            if (x == ex && y == ey) return ;
        }
    }
}
int main()
{
    cin >> m >> n;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < m; ++ j)
        {
            cin >> ma[i][j];
            if (ma[i][j] == 'K') sx = i, sy = j;
            if (ma[i][j] == 'H') ex = i, ey = j;
        }

    bfs(sx, sy);

    cout << dis[ex][ey] << endl;

    return 0;
}


活动打卡代码 AcWing 1076. 迷宫问题

ghy
18天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

typedef pair<int, int> PII;

const int N = 1010, M = N * N;

int n;
int m[N][N];
bool st[N][N];
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

PII q[M];
PII path[N][N];
PII nextLoca[N][N];


void bfs(int sx, int sy)
{
    int hh = 0, tt = -1;
    q[++ tt] = {sx, sy};
    st[sx][sy] = true;

    while (tt >= hh)
    {
        PII t = q[hh ++];
        int xx = t.first, yy = t.second;
        for (int i = 0; i < 4; ++ i)
        {
            int x = xx + dx[i], y = yy + dy[i];
            if (x < 0 || x >= n || y < 0 || y >= n || st[x][y] || m[x][y]) continue;

            st[x][y] = true;
            q[++ tt] = {x, y};
            nextLoca[x][y] = {xx, yy};
        }
    }
}
int main()
{
    cin >> n;
    for (int i = 0; i < n; ++ i)
        for (int j = 0;j < n; ++ j)
            cin >> m[i][j];

    nextLoca[n - 1][n - 1] = {n - 1, n - 1};
    bfs(n - 1, n - 1);

    PII t = {0, 0};
    while (1)
    {
        int x = t.first, y = t.second;
        cout << x << ' ' << y << endl;
        if (x == n - 1 && y == n - 1) break;
        t = nextLoca[x][y];
    }

    return 0;
}