一个田螺突然就

转山转水转不出自我

发表于 更新于

树

94. 二叉树的中序遍历 HOT100 递归+迭代 morris
morris 不改结构（类似线索二叉树），官解
144. 二叉树的前序遍历 递归+迭代 morris:和中序只要改if (pre->right == nullptr) {
res.push_back(root->val);
145. 二叉树的后序遍历 递归+迭代 morris 把94中序的左右颠倒
层序 102. 二叉树的层序遍历 HOT100 递归+迭代
429. N 叉树的层序遍历 没啥区别
103. 二叉树的锯齿形层序遍历
LCR 151. 彩灯装饰记录 III		 102倒过来
107. 二叉树的层序遍历 II 和102没区别，倒过来就行
662. 二叉树最大宽度 bfs,注意越界ull dfs
958. 二叉树的完全性检验 层次遍历，空值也入队，当出队值为空时判断队列剩下元素是否都为空，为则完全二叉树 dfs 也可，和662类似
递归 199. 二叉树的右视图 HOT100 递归+迭代
104. 二叉树的最大深度 HOT100 递归+迭代
559. N 叉树的最大深度 递归+迭代
111. 二叉树的最小深度 递归（前序 后续）+迭代
226. 翻转二叉树
LCR 144. 翻转二叉树		 HOT100 递归+迭代
110. 平衡二叉树 后序（递归+迭代）+前序前序，时间复杂度
222. 完全二叉树的节点个数 完全二叉树性质 二分+位运算（官解）
1325. 删除给定值的叶子节点 后序
3693 · 克隆 N 叉树
1490. 克隆 N 叉树		 dfs or bfs
617. 合并二叉树 dfs or bfs
一篇文章带你吃透对称性递归(思路分析+解题模板+案例解读) 100. 相同的树 dfs+迭代
101. 对称二叉树 HOT100 递归+迭代 100升级
572. 另一棵树的子树 100+每个比对
前序+kmp，哈希树（官解思路）		 100升级
LCR 143. 子结构判断 dfs+迭代 和572类似，但注意不同
路径
非自顶向下：		 543. 二叉树的直径 HOT100 bfs+dfs
124. 二叉树中的最大路径和 HOT100 543升级版 带路径
1245(3686 · N 叉树的直径 - LintCode)
2246. 相邻字符不同的最长路径 124升级（微软面试)函数要带引用不然超时
687. 最长同值路径
自顶向下： 257. 二叉树的所有路径
112. 路径总和 bfs+dfs
113. 路径总和 II
LCR 153. 二叉树中和为目标值的路径		 112 输出路径版
129. 求根节点到叶节点数字之和 bfs+dfs 113改改
437. 路径总和 III HOT100 双dfs（可打印出所有路径） or 前缀和
988. 从叶结点开始的最小字符串
公共祖先 236. 二叉树的最近公共祖先 HOT100 dfs or 哈希存父节点(官解)
235. 二叉搜索树的最近公共祖先
构造 105. 从前序与中序遍历序列构造二叉树 HOT100 输出后序，迭代
106. 从中序与后序遍历序列构造二叉树 105迭代改为左右更改，从后往前
二叉搜索树 98. 验证二叉搜索树 HOT100 中序，中序迭代
230. 二叉搜索树中第K小的元素 HOT100 中序，中序迭代
多次查询，记录k（官解bst）
LCR 174. 寻找二叉搜索树中的目标节点 230倒过来
108. 将有序数组转换为二叉搜索树 HOT100 先序
450. 删除二叉搜索树中的节点 递归or迭代
701. 二叉搜索树中的插入操作 递归or迭代
LCR 155. 将二叉搜索树转化为排序的双向链表
426（要vip）		 中序（递归or迭代
538. 把二叉搜索树转换为累加树
1038. 从二叉搜索树到更大和树		 反中序（可morris
链表 114. 二叉树展开为链表 后序、后序迭代
序列化 297. 二叉树的序列化与反序列化 前序+bfs
652. 寻找重复的子树 序列化+dfs
建图（？） 863. 二叉树中所有距离为 K 的结点 用哈希存父节点变成图遍历（bfsor dfs）官解

3686 · 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
/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */

class Solution {
public:
    /**
     * @param root: the root of the tree
     * @return: Maximum diameter of the N-ary Tree
     */
    int dfs(UndirectedGraphNode * root,int& ans)
    {
        if(!root)return 0;
        int l=0,r=0;
        for(auto nei:root->neighbors)
        {
            int cur=dfs(nei,ans);
            if(cur>l)
            {
                r=l,l=cur;
            }
            else if(cur>r)r=cur;
        }
        ans=max(l+r+1,ans);
        return max(l,r)+1;
    }
    int diameter(UndirectedGraphNode *root) {
        // write your code here
        if(!root)return 0;
        int ans=0;
        dfs(root,ans);
        return ans-1;
    }
};

二叉树的最近公共祖先(含输入)

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
#include<bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<endl
#define ll long long
using namespace std;
typedef unsigned long long ull;
const int N=1e3+10;
int n,p,q;
struct TreeNode 
{
    int val;
    int left;
    int right;
    TreeNode() : val(0), left(-1), right(-1) {}
    TreeNode(int x) : val(x), left(-1), right(-1) {}
//    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode nodes[N];

int lowestCommonAncestor(int root, int p, int q) {
        if(root==-1||root==p||root==q)return root;
        int lchild=lowestCommonAncestor(nodes[root].left,p,q);
        int rchild=lowestCommonAncestor(nodes[root].right,p,q);
        if(lchild!=-1&&rchild!=-1)
        {
            return root;
        }
        else if(lchild!=-1)
        {
            return lchild;
        }
        else if(rchild!=-1)
        {
            return rchild;
        }
        return -1;
    }
int main() 
{
    int n;
    scanf("%d%d%d", &n, &p, &q);
    for (int i = 0; i < n; i++) 
    {
        scanf("%d%d", &nodes[i].left, &nodes[i].right);
    }
    printf("%d", lowestCommonAncestor(0, p, q));
    return 0;
}

先序中序还原二叉树(后序输出)

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
#include<bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<endl
#define ll long long
using namespace std;
typedef unsigned long long ull;
const int N=1e3+10;
int n;
struct TreeNode 
{
    int val;
    TreeNode * left;
    TreeNode * right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    // TreeNode() : val(0), left(-1), right(-1) {}
    // TreeNode(int x) : val(x), left(-1), right(-1) {}
   TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
TreeNode nodes[N];

vector<int> pre, in, post;

    TreeNode * buildTree(int preL, int preR, int inL, int inR) 
    {
        if (preL > preR) 
        {
            return nullptr;
        }
        TreeNode* root=new TreeNode(pre[preL]);
        int inIndexOfRoot;
        for (int i = inL; i <= inR; i++) 
        {
            if (in[i] == root->val) 
            {
                inIndexOfRoot = i;
                break;
            }
        }
        int leftCount = inIndexOfRoot - inL;
        root->left = buildTree(preL + 1, preL + leftCount, inL, inIndexOfRoot - 1);
        root->right = buildTree(preL + leftCount + 1, preR, inIndexOfRoot + 1, inR);
        return root;
    }
void postOrder(TreeNode * root) 
{
    if (root == nullptr) 
    {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    post.push_back(root->val);
}
int main() {
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) 
    {
        scanf("%d", &x);
        pre.push_back(x);
    }
    for (int i = 0; i < n; i++) 
    {
        scanf("%d", &x);
        in.push_back(x);
    }
    TreeNode * root = buildTree(0, n - 1, 0, n - 1);
    postOrder(root);
    for (int i = 0; i < (int)post.size(); i++) 
    {
        printf("%d", post[i]);
        if (i < (int)post.size() - 1) 
        {
            printf(" ");
        }
    }
    return 0;
}

3693 · 克隆 N 叉树

dfs

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
/**
 * Definition of NBranchTree:
 * class NBranchTree {
 * public:
 *     int val;
 *     vector<NBranchTree> children;
 *     NBranchTree(int _val) {
 *         this->val = val;
 *     }
 *     NBranchTree(int _val, vector<NBranchTree*> _children) {
 *         val = _val;
 *         children = _children;
 *     }
 * };
 */

class Solution {
public:
    /**
     * @param root: The root node of a n-branch tree.
     * @return: The cloned tree.
     */
    NBranchTree* cloneTree(NBranchTree *root) {
        // --- write your code here ---
        if(!root)return nullptr;
        vector<NBranchTree*> chr;
        for(auto x:root->children)
        {
            NBranchTree* child=cloneTree(x);
            chr.push_back(child);
        }
        return new NBranchTree(root->val,chr);
    }
};

bfs

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
/**
 * Definition of NBranchTree:
 * class NBranchTree {
 * public:
 *     int val;
 *     vector<NBranchTree> children;
 *     NBranchTree(int _val) {
 *         this->val = val;
 *     }
 *     NBranchTree(int _val, vector<NBranchTree*> _children) {
 *         val = _val;
 *         children = _children;
 *     }
 * };
 */
#define debug(a) cout<<#a<<"="<<a<<" "
class Solution {
public:
    /**
     * @param root: The root node of a n-branch tree.
     * @return: The cloned tree.
     */
     unordered_map<NBranchTree *,NBranchTree *>umap;
    NBranchTree* cloneTree(NBranchTree *root) {
        // --- write your code here ---
        if(!root)return nullptr;
        vector<NBranchTree*> chr;
        queue<NBranchTree*>q;

        q.push(root);
        NBranchTree* head=nullptr;
        while(!q.empty())
        {
            int size=q.size();
           
            for(int i=0;i<size;i++)
            {
                NBranchTree* node=q.front();
                q.pop();
                NBranchTree* clonenode=new NBranchTree(node->val);
               
                // debug(clonenode->val);
                if(umap.count(node))
                { 
                    NBranchTree* parent = umap[node];
                    (parent->children).push_back(clonenode);
                }
                else
                {
                    head=clonenode;
                }
                for(auto x:node->children)
                {
                    umap[x]=clonenode;
                    q.push(x);
                }
                
            }
        }
        return head;
    }
};

谷歌面试（线段树/区间树）

Problem:

Given a list of timestamp ranges, each range represents a user using a Google service. Write a function that returns all users using the Google services at specific query timestamp.

A range can be represented as: [starting, ending], e.g., [1, 3] or [0, 10] and so on.

For instance, given a list of ranges:

[0, 5]
[6, 8]
[2, 9]
[4, 10]
[3, 5]

Searching through the above with a query timestamp of 3 should return:

[0, 2, 4]

because [0, 5], [2, 9], [3, 5] contain timestamp 3.

You’ll need to do a large number of queries through a largely static set of ranges that are provided at the start of the program.
It’s fine to prepare the data in some way such that the search operation is fast.

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory>

using namespace std;

// 定义区间结构，增加 id 以便追踪原始用户
struct Interval {
    int start;
    int end;
    int id; // 用户下标
};

// 区间树节点
struct Node {
    int center;
    Node* left = nullptr;
    Node* right = nullptr;
    
    // 存储经过该节点中心点的区间
    vector<Interval> by_start; // 按 start 升序
    vector<Interval> by_end;   // 按 end 降序

    ~Node() {
        delete left;
        delete right;
    }
};

class IntervalTree {
private:
    Node* root;

    // 递归构建树
    Node* build(const vector<Interval>& intervals) {
        if (intervals.empty()) return nullptr;

        // 1. 确定中心点 (使用中点，也可优化为中位数)
        int min_t = intervals[0].start;
        int max_t = intervals[0].end;
        for (const auto& i : intervals) {
            min_t = min(min_t, i.start);
            max_t = max(max_t, i.end);
        }
        int center = min_t + (max_t - min_t) / 2;

        vector<Interval> lefts;
        vector<Interval> rights;
        vector<Interval> overlaps;

        // 2. 将区间分发到左、右或中间
        for (const auto& i : intervals) {
            if (i.end < center) {
                lefts.push_back(i);
            } else if (i.start > center) {
                rights.push_back(i);
            } else {
                overlaps.push_back(i);
            }
        }

        Node* node = new Node();
        node->center = center;

        // 3. 处理中间重叠的区间
        // 按 start 升序排序
        node->by_start = overlaps;
        sort(node->by_start.begin(), node->by_start.end(), [](const Interval& a, const Interval& b) {
            return a.start < b.start;
        });

        // 按 end 降序排序 (便于 t > center 时快速截断)
        node->by_end = overlaps;
        sort(node->by_end.begin(), node->by_end.end(), [](const Interval& a, const Interval& b) {
            return a.end > b.end;
        });

        // 4. 递归构建左右子树
        // 注意：防止死循环，如果区间全部聚在中间，则不再递归
        if (!lefts.empty()) node->left = build(lefts);
        if (!rights.empty()) node->right = build(rights);

        return node;
    }

    // 递归查询
    void query(Node* node, int t, vector<int>& results) {
        if (!node) return;

        if (t < node->center) {
            // 情况 1: 查询时间在中心点左侧
            // 检查重叠区：因为这些区间都覆盖 center，即 end >= center > t 必然成立
            // 我们只需要找 start <= t 的区间
            for (const auto& i : node->by_start) {
                if (i.start > t) break; // 因为是升序，后面的肯定也不满足，直接 break 剪枝
                results.push_back(i.id);
            }
            // 继续去左子树找
            query(node->left, t, results);
        } 
        else if (t > node->center) {
            // 情况 2: 查询时间在中心点右侧
            // 检查重叠区：因为这些区间都覆盖 center，即 start <= center < t 必然成立
            // 我们只需要找 end >= t 的区间
            for (const auto& i : node->by_end) {
                if (i.end < t) break; // 因为是降序，后面的肯定更小，直接 break 剪枝
                results.push_back(i.id);
            }
            // 继续去右子树找
            query(node->right, t, results);
        } 
        else {
            // 情况 3: t == center
            // 所有重叠区间的区间都包含 center，直接全部加入
            for (const auto& i : node->by_start) {
                results.push_back(i.id);
            }
            // 不需要查左右子树了，因为左子树 end < center，右子树 start > center
        }
    }

public:
    // 构造函数：接收原始数据并预处理
    IntervalTree(const vector<pair<int, int>>& raw_ranges) {
        vector<Interval> intervals;
        for (int i = 0; i < raw_ranges.size(); ++i) {
            intervals.push_back({raw_ranges[i].first, raw_ranges[i].second, i});
        }
        root = build(intervals);
    }

    ~IntervalTree() {
        delete root;
    }

    // 对外接口
    vector<int> search(int timestamp) {
        vector<int> results;
        query(root, timestamp, results);
        // 题目要求的输出顺序往往是索引顺序，如果需要排序可以在这里 sort
        sort(results.begin(), results.end()); 
        return results;
    }
};

int main() {
    // 测试数据
    vector<pair<int, int>> ranges = {
        {0, 5},
        {6, 8},
        {2, 9},
        {4, 10},
        {3, 5}
    };

    // 1. 预处理数据 (Build)
    IntervalTree tree(ranges);

    // 2. 执行查询
    int query_time = 3;
    vector<int> result = tree.search(query_time);

    // 输出结果
    cout << "Users active at time " << query_time << ": [ ";
    for (int id : result) {
        cout << id << " ";
    }
    cout << "]" << endl;

    return 0;
}

比较两棵树中序遍历结果是否一致

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
class Solution {
public:
    bool isSameInorderSequence(TreeNode* root1, TreeNode* root2) {
        stack<TreeNode*> st1, st2;
        
        while (root1 != nullptr || !st1.empty() || root2 != nullptr || !st2.empty()) {
            // 1. 尽可能向左走，把沿途节点压入栈中
            while (root1 != nullptr) {
                st1.push(root1);
                root1 = root1->left;
            }
            while (root2 != nullptr) {
                st2.push(root2);
                root2 = root2->left;
            }

            // 2. 检查结构：如果此时一个栈为空而另一个不为空，说明节点数量或结构不一致
            if (st1.empty() || st2.empty()) {
                return false; 
            }

            // 3. 取出当前节点（中序遍历到的节点）
            root1 = st1.top(); st1.pop();
            root2 = st2.top(); st2.pop();

            // 4. 比较数值：如果不相等，直接返回 false
            if (root1->val != root2->val) {
                return false;
            }

            // 5. 转向右子树
            root1 = root1->right;
            root2 = root2->right;
        }

        return true;
    }
};

发表于 更新于

搜索

flood fill

1097. 池塘计数（poj2386）

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};
char g[maxn][maxn];
int ans=0;
int n=0,m=0;
void dfs(int x,int y)
{
    int dx=0,dy=0;
    for(int i=0;i<8;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&g[dx][dy]=='W')
        {
            g[dx][dy]='.';
            dfs(dx,dy);
        }
    }

}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(g[i][j]=='W')
            {
                dfs(i,j);
                ans++;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

1098.城堡计数

dfs

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
// 注意需要dfs返回，不能参数计算不然可能漏方向//

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[4][2]={{0,-1},{-1,0},{0,1},{1,0}};
int g[maxn][maxn],d[maxn][maxn][4],st[maxn][maxn];
int ans=0,room=0;
int n=0,m=0;
int dfs(int x,int y)
{
    int dx=0,dy=0;
    int cnt=1;
    for(int i=0;i<4;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&!d[x][y][i]&&!st[dx][dy])
        {

            st[dx][dy]=1;
            cnt+=dfs(dx,dy);
        }
    }
    return cnt;

}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>g[i][j];
            for(int k=0;k<4;k++)
            {
                if(g[i][j]>>k&1)
                {
                    d[i][j][k]=1;
                }
            }
        }
    }
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {

            if(st[i][j])continue;
            st[i][j]=1;
            room++;
            ans=max(ans,dfs(i,j));

        }
    }
    cout<<room<<endl;
    cout<<ans<<endl;
    return 0;
}

bfs

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=100086;
int e[INF],a[INF],ne[INF],h[INF],q[INF],idx,n,m; 
int  g[60][60],d[60][60];
typedef pair<int,int >PII;
int space,ans;
int dir[5][3]={{0,-1},{-1,0},{0,1},{1,0}};
void bfs(int x,int y)
{
	queue<PII>q;
	int space1=0;
	d[x][y]=1;
	q.push({x,y});
	int dx=0,dy=0;
	//cout<<x<<","<<y<<endl;
	while(q.size()>0)
	{
		auto t=q.front();
		q.pop();
		int x = t.first, y = t.second ;
		space1++;
		for(int i=0;i<4;i++)
		{//cout<<g[x][y]<<" "<<(g[x][y]>>i&1)<<endl;
		    if(!(g[x][y]>>i&1))
		    {
			    dx=t.first+dir[i][0];
        	    dy=t.second+dir[i][1];
        	    
        	    if(dx>=0&&dx<n&&dy>=0&&dy<m&&!d[dx][dy])
        	    {
        		   // cout<<" "<<dx<<", "<<dy<<endl;
        		    d[dx][dy]=1;
        	    //	pprev[dx][dy]=t;
        		    q.push({dx,dy});
        		    
			    }
		    }
		}
		
	}
	space=max(space,space1);
	return ;
	
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n>>m;

	//memset(d,-1,sizeof(d));
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			cin>>g[i][j];
		}
	}
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(!d[i][j])
			{
				bfs(i,j);
				ans++;
			}
		}
	}
	cout<<ans<<endl;
	cout<<space<<endl;
	return 0;	
}

1106. 山峰和山谷(poi2007)

dfs

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
const int N = 1E3 + 10;
int g[N][N];
int vis[N][N];
int n;
int isp, isv;
int dir[8][2]={{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};
void dfs(int x, int y)
{
    for(int i = 0; i < 8; i ++ )
    {
        int dx = x + dir[i][0], dy = y + dir[i][1];
        if(!(dx>=0&&dx<n&&dy>=0&&dy<n))  continue;
        if(g[dx][dy] > g[x][y]) isp = 0;
        else if(g[dx][dy] < g[x][y])    isv = 0;
        else if(g[dx][dy] == g[x][y]&&vis[dx][dy] == 0)
        {

            vis[dx][dy] = 1;
            dfs(dx, dy);
        }
    }
}
int main()
{
    cin >> n;
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            cin >> g[i][j];
        }

    }
    int peak = 0, valley = 0;
    for(int i = 0; i < n; i ++ )
    {
        for(int j = 0; j < n; j ++ )
        {
            if(vis[i][j])   continue;
            isp = 1, isv = 1;
            vis[i][j] = 1;
            dfs(i, j);
            if(isp)peak++;
            if(isv)valley++;
//            peak += isp;
//            valley += isv;
        }
    }
    cout << peak << ' ' << valley << endl;
    return 0;
}

bfs

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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1010;
int d[INF][INF],n,m,ans; 
int g[INF][INF];
typedef pair<int,int >PII;
PII pprev[INF][INF];
int dir[10][3]={{0,0},{-1, -1}, {-1, 0}, {-1, 1}, {0, -1},
    {0, 1}, {1, -1}, {1, 0}, {1, 1}};
void bfs(int x,int y,int& isp,int& isv)
{
	int dx=0,dy=0;
	//cout<<x<<","<<y<<endl;
	queue<PII >q;
	q.push({x,y});
	d[x][y]=1;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=1;i<=8;i++)
		{
			dx=t.first+dir[i][0];
        	dy=t.second+dir[i][1];
			if(!(dx>=0&&dx<n&&dy>=0&&dy<n))continue;
			
        	if(g[dx][dy]==g[t.first][t.second]&&!d[dx][dy])
        	{
        		//cout<<" "<<dx<<", "<<dy<<endl;
        		//	pprev[dx][dy]=t;
        		q.push({dx,dy});
				d[dx][dy]=1;
			}	
			if(g[dx][dy]>g[t.first][t.second])
			{
				isp=0;
				//d[dx][dy]=1;
				//cout<<" isp"<<dx<<","<<dy<<endl;
			}
			if(g[dx][dy]<g[t.first][t.second])
			{
				isv=0;
				//d[dx][dy]=1;
				//cout<<" isv"<<dx<<","<<dy<<endl;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	cin>>n;
	for(int i=0;i<n;i++)
    	for(int j=0;j<n;j++)
    		cin>>g[i][j];
	int peak=0,valley=0;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)
    	{
    		if(d[i][j])continue;
    		int isp=1,isv=1;
    		bfs(i,j,isp,isv);
    		if(isp)peak++;
    		if(isv)valley++;
		}
	}    		
    
	cout << peak << " " << valley << endl;
	 
	return 0;	
}

最短路模型

188. 武士风度的牛

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
const int N=1010;
int dir[8][2]={{1,2},{2,1},{-1,-2},{-2,-1},{1,-2},{2,-1},{-1,2},{-2,1} };
char g[N][N];
int dis[N][N];
int endx,endy,n,m,ans,sx,sy;
void bfs(int x,int y)
{
	int dx=0,dy=0;
	queue<pii>q;
	q.push({x,y});
	dis[x][y]=1;
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<8;i++)
		{
			int dx=t.first+dir[i][0];
			int dy=t.second+dir[i][1];
			if(!(dx>=0&&dx<n&&dy>=0&&dy<m))continue;
			if(g[dx][dy]=='*')continue;
//			cout<<dx<<","<<dy<<endl;
			if(dis[dx][dy]!=0)continue;
			dis[dx][dy]=dis[t.first][t.second]+1;
			q.push({dx,dy});
//			cout<<dis[dx][dy]<<endl;
			if(dx==endx&&dy==endy)
			{
				ans=dis[dx][dy];
				return ;
			}
		}
	}
}

int main()
{
    cin>>m>>n;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<m;j++)
    	{
    		cin>>g[i][j];
		}
	}
	for(int i=0;i<n;i++)
    {
    	for(int j=0;j<m;j++)
    	{
    		if(g[i][j]=='K')
    		{
    			sx=i,sy=j;
//    			cout<<sx<<",   "<<sy<<endl;
//    			break;
			}
			else if(g[i][j]=='H')
    		{
    			endx=i;
    			endy=j;
			}
		}
	}
	bfs(sx,sy);
//	cout<<sx<<",   "<<sy<<endl;
	cout<<ans-1<<endl;
    return 0;
}

1100. 抓住那头牛

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
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
typedef long long ll;
const int N=1e5+10;
int n,m,k;
int a[100086];
int b[100086];
int zhuan(int i,int x)
{
	if(i==0)return x-1;
	if(i==1)return x+1;
	if(i==2)return 2*x;
}
int bfs()
{
	queue<int >q;
//	unordered_map<string,int >d;
	q.push(n);
	b[n]=0;
	a[n]=1;
	while(q.size())
	{
		int t=q.front();
		q.pop();
		if(t==k)return b[k];
		for(int i=0;i<3;i++)
		{
			int xx=zhuan(i,t);
			
			if(xx>=0&&xx<=100000&&!a[xx])
			{
				q.push(xx);
				a[xx]=1;
				b[xx]=b[t]+1;
			}
//			cout<<xx<<','<<yy<<endl;
		}
	}
	return 0;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

	cin>>n>>k;
	cout<<bfs()<<endl;
	return 0;	
}

多源bfs

173. 矩阵距离

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair<int,int>pii;
const int N=1010;
int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
char g[N][N];
int dis[N][N];
int endx,endy,n,m,ans,sx,sy;
void bfs()
{
	int dx=0,dy=0;
	queue<pii>q;
	for(int x=0;x<n;x++)
	{
		for(int y=0;y<m;y++)
		{
			if(g[x][y]=='1')
			{
				q.push({x,y});
				dis[x][y]=1;
			}
			
		}
	}
	
	while(q.size())
	{
		auto t=q.front();
		q.pop();
		for(int i=0;i<4;i++)
		{
			int dx=t.first+dir[i][0];
			int dy=t.second+dir[i][1];
			if(!(dx>=0&&dx<n&&dy>=0&&dy<m))continue;
			if(g[dx][dy]=='1')continue;
//			cout<<dx<<","<<dy<<endl;
			if(dis[dx][dy]!=0)continue;
			dis[dx][dy]=dis[t.first][t.second]+1;
			q.push({dx,dy});
//			cout<<dis[dx][dy]<<endl;
			
		}
	}
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<m;j++)
    	{
    		cin>>g[i][j];
		}
	}
	
	bfs();
//	cout<<sx<<",   "<<sy<<endl;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
    	{
    		cout<<dis[i][j]-1<<" ";
		}
		cout<<endl;
	}
    return 0;
}

最小步数模型

1107. 魔板

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
85
86
87
88
89
90
91
92
93
94
95
96
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=110;
int d[INF][INF],n,m; 
int g[INF][INF];
typedef pair<int,int >PII;
PII pprev[INF][INF];
unordered_map< string, int >dist;
unordered_map<string, pair<char, string > >ppre;
string move0(string t)
{
	for(int i=0;i<4;i++)
	{
		swap(t[i],t[7-i]);
	}
	return t;
}
string move1(string t)
{
	for(int i=0;i<3;i++) swap(t[3],t[i]);
    for(int i=4;i<7;i++) swap(t[i],t[i+1]);
    return t;
}
string move2(string t)
{
	swap(t[1],t[2]),swap(t[5],t[6]),swap(t[1],t[5]);
    return t;
}
void bfs(string start,string end)
{
	//cout<<start<<endl;
	//cout<<end<<endl;
	queue<string>q;
	
	q.push(start);
	dist[start]=0;
	
	while(q.size()>0)
	{
		auto t=q.front();
		q.pop();
		if(t==end)break;
		string m[3];
		m[0]=move0(t);
		m[1]=move1(t);
		m[2]=move2(t);
		for(int i=0;i<3;i++)
		{
			string dm=m[i];
			
        	if(dist.count(dm)==0)
        	{
        		dist[dm]=dist[t]+1;
        		ppre[dm]={char(i+'A'),t};
        		if(dm==end)break;
        		q.push(dm);
        	//	cout<<dm<<endl;
			}
			
		}
	}
	cout<<dist[end]<<endl;
	string res;
	if(!dist[end])return;
	while(end!=start)
	{
		res+=ppre[end].first;
		end=ppre[end].second;
	}
	reverse(res.begin(),res.end());
	cout<<res<<endl;
	return ;
	
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int x=0;
	string start,end;
	for(int i=0;i<8;i++)
	{
		cin>>x;
		end+=char(x+'0'); 
	}
	for(int i=0;i<8;i++)
	{
		start+=char(i+'1');
	}
	bfs(start,end);
	
	return 0;	
}

双端队列广搜

175. 电路维修

https://www.acwing.com/solution/content/21775/

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
85
86
87
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=510;
int d[INF][INF],st[INF][INF],n,m; 
char g[INF][INF];
typedef pair<int,int >PII;
PII pprev[INF][INF];
int dir[5][3]={{-1,-1},{-1,1},{1,1},{1,-1}};
int ixy[5][3]={{-1,-1},{-1,0},{0,0},{0,-1}};

int bfs()
{
	
	deque<PII>q;
	memset(d,0x3f,sizeof(d));
	memset(st,0,sizeof(st));
	q.push_front({0,0});
	char ch[5]="\\/\\/";
	
	d[0][0]=0;
	
	while(q.size()>0)
	{
		auto t=q.front();
		q.pop_front();
		int a=t.first,b=t.second;
		if(a==n&&b==m)
		{
			return d[n][m];
		}
		if(st[a][b])continue;
		st[a][b]=1;
		for(int i=0;i<=3;i++)
		{
			int dx=a+dir[i][0];
			int dy=b+dir[i][1];
			if(dx<0||dx>n||dy<0||dy>m)continue;
			int w=0;
			int cx=a+ixy[i][0];
			int cy=b+ixy[i][1];
			if(g[cx][cy]!=ch[i])
			{
				w=1;
			}
			int dw=d[a][b]+w;
        	if(dw<d[dx][dy])
        	{
        		d[dx][dy]=dw;

        	    if(w)q.push_back({dx,dy});
        	    else q.push_front({dx,dy});
			}
		}
	}

	return -1;
	
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int t=0;
    cin>>t;
    while(t--)
    {
    	cin>>n>>m;
    	for(int i=0;i<n;i++)
    	{
    		for(int j=0;j<m;j++)
    		{
    			cin>>g[i][j];
			}
		}
		if((n+m)&1)cout<<"NO SOLUTION"<<endl;
		else
		{
			cout<<bfs()<<endl;
		}
	}
	
	
	return 0;	
}

双向BFS

190. 字串变换

https://www.acwing.com/solution/content/61327/

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef pair<int,int>pii;
const int N=7;
string a[N],b[N],sa,sb;
unordered_map<string,int> qa,qb;
queue<string> q1,q2;
int n,t;
int extend(queue<string> &q,unordered_map<string,int> &qa,unordered_map<string,int> &qb,string a[],string b[])
{
    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 nw=t.substr(0,i)+b[j]+t.substr(i+a[j].size());

                if(qb.count(nw)) return qa[t]+1+qb[nw];
                if(qa.count(nw)) continue;

                q.push(nw);
                qa[nw]=qa[t]+1;
            }
        }
    }
    return 11;
}
int bfs(string sa,string sb)
{
	int t=0;
	if(sa==sb)return 0;
	qa[sa]=0;
	q1.push(sa);
	qb[sb]=0;
	q2.push(sb);
	while(q1.size()&&q2.size())
	{
		if(q1.size()<q2.size())t=extend(q1,qa,qb,a,b);
		else t=extend(q2,qb,qa,b,a);
		if(t<=10 )return t;
	}
	return 11;
	
}

int main()
{
	cin>>sa>>sb;
    if(sa == sb)
	{
	    cout << 0 << '\n';
	    return 0;
	}
	while(cin>>a[n]>>b[n])
	{
		n++;
	}
	int t=bfs(sa,sb);
	if(t>10)
	{
		cout<<"NO ANSWER!"<<endl;
	}
	else
	{
		cout<<t<<endl;
	}
    return 0;
}

lc127. 单词接龙

Astar

178. 第K短路

评论

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
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef pair <int,int> PII;
typedef pair <int,PII> PIII;
const int N=1010,INF=0x3f3f3f3f;
int dist[N],cnt[N];
int st[N];
int n,m;
int a,b,c;
int tt,ss,k;
struct edge
{
    int to;
    int length;
    edge(int t,int l):to(t),length(l){}
};
vector<PII>graph[N];
vector<PII>rgraph[N];
void dij()
{
    memset(dist, 0x3f, sizeof dist);
    dist[tt] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({0, tt});      // first存储距离，second存储节点编号

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

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

        for (int i = 0;i<rgraph[ver].size();i++)
        {
            int j = rgraph[ver][i].first;
            int w=rgraph[ver][i].second;
            if (dist[j] > distance + w)
            {
                dist[j] = distance + w;
                heap.push({dist[j], j});
            }
        }
    }
    
}
int astar()
{
	priority_queue <PIII,vector <PIII>,greater <PIII>> heap;
	heap.push({dist[ss],{0,ss}});
	while(heap.size())
	{
		auto t=heap.top();
		heap.pop();
		int ver=t.second.second,distance=t.second.first;
		cnt[ver]++;
		if(cnt[tt]==k)return distance;
		for(int i = 0;i<graph[ver].size();i++)
		{
			int j = graph[ver][i].first;
			int w = graph[ver][i].second;
			if(dist[j]<INF)
			{
				heap.push({distance+w+dist[j],{distance+w,j}});
				
			}
		}
	}
	return -1;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
    	cin>>a>>b>>c;
    	graph[a].push_back({b, c});
        rgraph[b].push_back({a, c});
	}
	cin>>ss>>tt>>k;
	if(ss==tt)k++;
	dij();
	cout<<astar()<<endl;
    return 0;
}

179. 八数码

https://www.acwing.com/solution/content/35528/

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
#include<unordered_map>
using namespace std;
typedef pair <int,string> PII;
typedef pair <int,PII> PIII;
const int N=1010,INF=0x3f3f3f3f;
int dist[N],cnt[N];
int st[N];
int n,m;

int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
string c,start,x;

int f(string m)
{
	int dt=0;
	for(int i=0;i<9;i++)
	{
		if(m[i]!='x')
		{
			int t=m[i]-'1';
			dt=dt+abs(i/3-t/3)+abs(i%3-t%3);
		}
	}
	return dt;
}
string bfs()
{
	priority_queue<PII, vector<PII>, greater<PII>> heap;//小根堆,将元素的估计终点距离从小到大排序
	unordered_map<string,int >d;
	unordered_map<string,pair<string,char>> last;//存储一个元素由哪种状态,经过哪种操作得来,跟前面几题一样
	heap.push({f(start),start});
	char op[]="udlr";
	string end="12345678x";//终点
	d[start]=0;
	while(heap.size())
	{
		auto t=heap.top();
		heap.pop();
		string state=t.second;
		int cnt=d[state];
		if(t.second=="12345678x")break;
		int pos=state.find('x');
		int dx=pos/3,dy=pos%3;
		string init=state;
		for(int i=0;i<4;i++)
		{
			int xx=dx+dir[i][0];
			int yy=dy+dir[i][1];
			if(xx>=0&&xx<3&&yy>=0&&yy<3)
			{
				swap(state[pos],state[xx*3+yy]);
				if(!d.count(state)||d[state]>d[init]+1)
				{
					d[state]=d[init]+1;
					heap.push({f(state)+d[state],state});
					last[state]={init,op[i]};
				}
				swap(state[pos],state[xx*3+yy]);
			}
//			cout<<xx<<','<<yy<<endl;
		}
	}
	string ans;
	while(end!=start)
	{
		ans+=last[end].second;
		end=last[end].first;
	}
	reverse(ans.begin(),ans.end());//将其反转
	return ans;
}
int main()
{
	ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	for(int i=0;i<9;i++)
	{
		cin>>c;
		start+=c;
		if(c!="x") x+=c;		
	}
	 int res=0;//统计逆序对的数量
    for(int i=0;i<8;i++)
    	for(int j=i+1;j<8;j++)
    		if(x[i]>x[j]) 
       			res++;

    if(res%2) printf("unsolvable\n");//如果逆序对为奇数,就不可能抵达终点
    else
	cout<<bfs()<<endl;
	return 0;	
}

DFS之连通性模型(flood fill)

1112. 迷宫

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char g[maxn][maxn];
int ans=0,k;
int n=0,ex,ey,sy,sx;
int dfs(int x,int y)
{
    int dx=0,dy=0;
    if(x==ex&&y==ey)return 1;
    for(int i=0;i<4;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<n&&g[dx][dy]!='#')
        {
            g[dx][dy]='#';
            if(dfs(dx,dy))return 1;
        }
    }
    return 0;

}
int main()
{
	cin>>k;
	while(k--)
	{
		cin>>n;
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<n;j++)
	        {
	            cin>>g[i][j];
	        }
	    }
	    cin>>sx>>sy>>ex>>ey;
	    if(g[sx][sy] == '#' || g[ex][ey] == '#')
	    {
	    	cout<<"NO"<<endl;
	    	continue;
		}
	    if(dfs(sx,sy))cout<<"YES"<<endl;
	    else cout<<"NO"<<endl;
	}
    
    return 0;
}

1113. 红与黑

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
//
// Created by wyh on 2023/7/18.
//
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
char g[maxn][maxn];
int st[maxn][maxn];
int ans=0;
int n=0,m=0;
int dfs(int x,int y)
{
    int dx=0,dy=0;
    int cnt=1;
    for(int i=0;i<4;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&g[dx][dy]!='#'&&!st[dx][dy])
        {
            st[dx][dy]=1;
            cnt+=dfs(dx,dy);
        }
    }
	return cnt;
}
int main()
{
	while(1)
	{
		cin>>m>>n;
		if(!m&&!n)break;
		memset(st,0,sizeof(st));
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            cin>>g[i][j];
	        }
	    }
	    for(int i=0;i<n;i++)
	    {
	        for(int j=0;j<m;j++)
	        {
	            if(g[i][j]=='@')
	            {
	            	st[i][j]=1;
	                ans=dfs(i,j);
//	                break;
	            }
	        }
	    }
	    cout<<ans<<endl;
	}
    
    return 0;
}

DFS之搜索顺序

1116. 马走日

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
//char g[maxn][maxn];
int st[maxn][maxn];
int ans=0;
int n=0,m=0,k,sx,sy;
void dfs(int x,int y,int t)
{
    int dx=0,dy=0;
    int cnt=1;
    if(t==n*m)
    {
    	ans++;
    	return;
	}
    for(int i=0;i<8;i++)
    {
        dx=x+dir[i][0];
        dy=y+dir[i][1];
        if(dx>=0&&dx<n&&dy>=0&&dy<m&&!st[dx][dy])
        {
            st[dx][dy]=1;
            dfs(dx,dy,t+1);
            st[dx][dy]=0;
        }
    }
	
}
int main()
{
	cin>>k;
	while(k--)
	{
		ans=0;
		cin>>n>>m>>sx>>sy;
//		sx++,sy++;
//		if(!m&&!n)break;
		memset(st,0,sizeof(st));
	    st[sx][sy]=1;
	    dfs(sx,sy,1);
	   
	    cout<<ans<<endl;
	}
    
    return 0;
}

1117. 单词接龙

https://www.acwing.com/solution/content/59984/

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
int g[maxn][maxn];
string word[maxn];
int used[maxn];
int ans=0;
int n=0,m=0,k,sx,sy;
void dfs(string dragon,int last)
{
    //法一：
// 	ans=max((int)dragon.size(),ans);
//	used[last]++;
	for(int i=0;i<n;i++)
	{
		if(g[last][i]&&used[i]<2)
		{
		    ans=max((int)(dragon+word[i].substr(g[last][i])).size(),ans);
			used[i]++;
			
			dfs(dragon + word[i].substr(g[last][i]), i);
			used[i]--;
		}
	}
//	used[last]--;
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>word[i];
	}
    char sta;
    cin>>sta;
    for(int i=0;i<n;i++)
    {
    	for(int j=0;j<n;j++)
    	{
    		string a=word[i],b=word[j];
    		for(int k=1;k<min(a.size(),b.size());k++)
    		{
    			if(a.substr(a.size()-k,k)==b.substr(0,k))
    			{
    				g[i][j]=k;
    				break;
				}
			}
		}
	}
	for(int i=0;i<n;i++)
	{
		if(word[i][0]==sta)
		{
            //法一这两行不需要
		    ans=max((int)(word[i]).size(),ans);
			used[i]++;
			dfs(word[i],i);
		}
	}
	cout<<ans<<endl;
    return 0;
}

1118. 分成互质组

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,m=0,k,sx,sy;
vector<vector<int> > g;
int check(int c,int x)
{
	for(int i=0;i<g[c].size();i++)
	{
		if(__gcd(g[c][i],x)>1)return 0;
	}
	return 1;
}
void dfs(int u)
{
	if(g.size()>ans)return;
    if(u==n)
    {
    	ans=min(ans,(int)g.size());
    	return;
	}
	for(int i=0;i<g.size();i++)
	{
		if(check(i,a[u]))
		{
			g[i].push_back(a[u]);
			dfs(u+1);
			g[i].pop_back();
		}
	}
	g.push_back({a[u]});
	dfs(u+1);
	g.pop_back();
}
int main()
{
	cin>>n;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
	dfs(0);
	cout<<ans<<endl;
    return 0;
}

DFS之剪枝与优化

165. 小猫爬山

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;
int dir[8][2]={{-1,2},{1,2},{2,-1},{2,1},{-1,-2},{1,-2},{-2,-1},{-2,1}};
//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
vector<int>sum;
bool cmp(int a, int b) 
{
    return a > b;
}
void dfs(int u)
{
	if(sum.size()>=ans)return;
    if(u==n)
    {
    	ans=min(ans,(int)sum.size());
    	return;
	}
	for(int i=0;i<sum.size();i++)
	{
		if(sum[i]+a[u]<=w)
		{
// 			g[i].push_back(a[u]);
			sum[i]+=a[u];
			dfs(u+1);
// 			g[i].pop_back();
			sum[i]-=a[u];
		}
	}
// 	g.push_back({a[u]});
	sum.push_back({a[u]});
	dfs(u+1);
// 	g.pop_back();
	sum.pop_back();
}
int main()
{
	cin>>n>>w;
	for(int i=0;i<n;i++)
	{
		cin>>a[i];
	}
    //注意排序的剪枝
	sort(a,a+n,cmp);
	dfs(0);
	cout<<ans<<endl;
    return 0;
}

166. 数独

思路
数独一看就可以暴搜，但一看就会超时，所以考虑剪枝。

优化搜索顺序 ✔ ✔
可以优先搜索位置上能填的数最少的方格

排除等效冗余 ✖ ✖
因为整棵搜索树都会搜到，所以不能排除等效冗余
可行性剪枝 ✔ ✔
这一步可以放在枚举能放的位置上进行优化
由于每一行每一列每一个宫格都不能重复，所以我们可以用位运算优化枚举数的过程
最优化剪枝 ✖ ✖
这里我们无需考虑答案最小，只需考虑是否有解

改进
优化搜索顺序，每次优先搜索可选放入数字最少的空白格子，这样它下面搜索时的分支就会少
假设当前搜索到坐标为（x，y）的这个格子

  1. 先解释一下几个数组的含义
    row【i】表示第i行能放的数有哪些（1-9），是二进制表示的，9个位置上，1代表这个数能放，0代表不能放
    col【j】表示第j行能放的数有哪些（1-9），二进制表示同上
    cell【i】【j】—-这里把坐标看成是3*3的，（i，j）就指向了一个唯一的小型九宫格，也是二进制表示这个小型九宫格里能放的数有哪些
    这样我们在（x，y）这个位置上放的数就是满足行，列，小型九宫格都能放的数，取交集
    row[x]&col[y]&cell[x/3][ y/3 ]三者取交集—(x/3,y/3)是小型九宫格的位置

想到位运算优化，三个二进制数进行与运算，最后得到的二进制数中为1的位置，代表这个数能放进（x，y）这个空格子里

  1. 另一个位运算优化：lowbit（）
    lowbit()可以用来计算一个二进制数里面有多少个1
    lowbit举个例子：lowbit（x） x=10001000（二进制） 会返回1000（二进制）
    因为会返回1000，而不会返回我们想要直到的1在第几位，
    所以我们有额外开了数组map【】 1000->8->log2 8就是3,这样1000就会返回map【1000】=3

    map【100】=2

  2. 另外我们还需要看一下最后三者交集的二进制数结果里有多少个1，根据1的数目选择数目较少的先进行搜索，达到优化搜索顺序剪枝的目的：
    用ones【i】记录二进制数i里面有多少个1 (i属于【0,2的9次方-1】)

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<bits/stdc++.h>
#define debug(a) cout<<#a<<"="<<a<<endl
#define ll long long
const int N=9;

using namespace std;
typedef pair<int,int> pii;
int  mapp[1<<N],ones[1<<N];
int row[N],col[N],ma[3][3];
string str;
inline void init()
{
	for(int i=0;i<9;i++)
	{
		row[i]=col[i]=(1<<N)-1;
	}
	
	for(int i=0;i<3;i++)
	{
		for(int j=0;j<3;j++)
		{
			ma[i][j]=(1<<N)-1;
		}
	}
}
inline int lowbit(int x)
{
	return x&-x;
}
inline int get(int x,int y)
{
	return row[x]&col[y]&ma[x/3][y/3];
}
int dfs(int cnt)
{
	if(!cnt)return 1;
	int minv=10,x=0,y=0;
	for(int i=0;i<9;i++)
	{
		for(int j=0;j<9;j++)
		{
			if(str[i*9+j]=='.')
			{
				int t=ones[get(i,j)];
				if(t<minv)
				{
					minv=t;
					x=i;
					y=j;
				}
			}
			
		}
	}
	for(int i=get(x,y);i;i-=lowbit(i))
	{
		int t=mapp[lowbit(i)];
		row[x]-=(1<<t);
		col[y]-=(1<<t);
		ma[x/3][y/3]-=1<<t;
		str[x*9+y]='1'+t;
		if(dfs(cnt-1))return 1;
		row[x]+=(1<<t);
		col[y]+=(1<<t);
		ma[x/3][y/3]+=1<<t;
		str[x*9+y]='.';
	}
	return 0;
}
int main() 
{
	for(int i=0;i<9;i++)
	{
		mapp[1<<i]=i;
	}
	for(int i=0;i<1<<N;i++)
	{
		int s=0;
		for(int j=i;j;j-=lowbit(j))s++;
		ones[i]=s;
	}
    while(cin>>str)
    {
    	if(str=="end")break;
    	init();
    	int cnt=0;
    	for(int i=0,k=0;i<9;i++)
    	{
    		for(int j=0;j<9;j++,k++)
    		{
    			if(str[k]!='.')
    			{
    				int t=str[k]-'1';
    				row[i]-=1<<t;
    				col[j]-=1<<t;
    				ma[i/3][j/3]-=1<<t;
				}
				else
				{
					cnt++;
				}
			}
		}
		dfs(cnt);
		cout<<str<<endl;
	}
    return 0;
}

167. 木棒

code refer

剪枝策略

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int N=1010;
int len,sum,n,st[N],w[N];
bool cmp(int a, int b) 
{
    return a > b;
}
int dfs(int u,int s,int start)
{
	if(u*len==sum)return 1;
	if(s==len)return dfs(u+1,0,0);//易错
	for(int i=start;i<n;i++)
	{
		if(!st[i]&&s+w[i]<=len)
		{
			st[i]=1;
			if(dfs(u,s+w[i],i+1))return 1;
			st[i]=0;
			if(!s||s+w[i]==len)return 0;
			int j=i;
			while(j<n&&w[j]==w[i])j++;
			i=j-1;
		}
	 } 
	 return 0;
}
int main()
{
	while(cin>>n&&n)
	{
		memset(st,0,sizeof(st));
		sum=0,len=1;
		for(int i=0;i<n;i++)
		{
			cin>>w[i];
			sum+=w[i];
		}
		sort(w,w+n,cmp);
		while(1)
		{
			if(sum%len==0&&dfs(0,0,0))
			{
				cout<<len<<endl;
				break;
			}
			len++;
		}
		
	}
    return 0;
}

168. 生日蛋糕

https://www.acwing.com/solution/content/4187/

image-20230725173137592

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int N = 24, INF = 1e9;
const int maxn=1010;
//char g[maxn][maxn];
int n=0,m=0;
int res=INF,cnt;
int minv[maxn],mins[maxn],hh[maxn],rr[maxn];
void dfs(int u,int v,int s)
{
	if(v+minv[u]>n)return;//可行性
	
	if(s+mins[u]>=res)return;//最优解
	if(s+2*(n-v)/rr[u+1]>=res)return;
//	cout<<n<<" "<<m<<endl;
	if(!u)
	{
		if(v==n)res=s;
		return;
	} 
	for(int r=min(rr[u+1]-1,(int)sqrt((n-v)));r>=u;r--)
	{
		for(int h=min(hh[u+1]-1,(n-v)/r/r);h>=u;h--)
		{
			int t=0;
			//最底层的时候需要加上r*r
			if(u==m)t=r*r;
			rr[u]=r,hh[u]=h;
//			if(u==1)
//			cout<<u<<" "<<r<<" "<<h<<cnt++<<endl;
			dfs(u-1,v+r*r*h,s+2*r*h+t);
		}
	}
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		minv[i]=minv[i-1]+i*i*i;
		mins[i]=mins[i-1]+2*i*i;
	}
	//m+1层不存在，作为哨兵，减少边界情况的判断
	rr[m+1]=hh[m+1]=INF;
//	cout<<n<<m<<endl;
	dfs(m,0,0);
	if(res==INF)res=0;
	cout<<res<<endl;
    return 0;
}

迭代加深

170. 加成序列

​ 1

​ 2

4 3

8 6 5 6 5 4

不是同一层不能去重

写法1：

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;

//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
int path[maxn];

int dfs(int u,int depth)
{
	if(u>depth)return 0;
	if(u==depth)return path[u-1]==n;
	int st[maxn]={0};//定义在本层，只进行本层去重
	for(int i=u-1;i>=0;i--)
	{
		for(int j=i;j>=0;j--)
		{
			int s=path[i]+path[j];
			if(s > n || s <= path[u - 1] || st[s])continue;
			st[s]=1;
			path[u]=s;
			if(dfs(u+1,depth))return 1;
		}
	}
	return 0;
}
int main()
{
	path[0]=1;
	while(cin>>n&&n)
	{
		int dep=1;
		while(!dfs(1,dep))
		{
			dep++;
		}
		for(int i=0;i<dep;i++)
		{
			cout<<path[i]<<" ";
		}
		cout<<endl;
	}
    return 0;
}

写法2：

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;

//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
int path[maxn];
int st[maxn]={0};
int dfs(int u,int depth)
{
	if(u>depth)return 0;
	if(u==depth)return path[u-1]==n;
	
	for(int i=u-1;i>=0;i--)
	{
		for(int j=i;j>=0;j--)
		{
			int s=path[i]+path[j];
//			cout<<s<<endl;
			if(s > n || s <= path[u - 1] || st[s])continue;
//			cout<<s<<" u:"<<u<<" "<<path[u-1]<<" "<<depth<<endl;
			st[s]=1;
			path[u]=s;
			if(dfs(u+1,depth))return 1;
			st[s]=0;
		}
	}
	return 0;
}
int main()
{
	path[0]=1;
	while(cin>>n&&n)
	{
		int dep=1;
		memset(st,0,sizeof(st));
		while(!dfs(1,dep))
		{
			dep++;
			
		}
		for(int i=0;i<dep;i++)
		{
			cout<<path[i]<<" ";
		}
		cout<<endl;
	}
    return 0;
}

双向DFS

171. 送礼物

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=1010;

//char g[maxn][maxn];
int a[maxn];
int ans=100;
int n=0,w=0,k,sx,sy;
vector<vector<int> > g;
int path[maxn];
int st[maxn]={0};
int dfs(int u,int depth)
{
	if(u>depth)return 0;
	if(u==depth)return path[u-1]==n;
	
	for(int i=u-1;i>=0;i--)
	{
		for(int j=i;j>=0;j--)
		{
			int s=path[i]+path[j];
//			cout<<s<<endl;
			if(s > n || s <= path[u - 1] || st[s])continue;
//			cout<<s<<" u:"<<u<<" "<<path[u-1]<<" "<<depth<<endl;
			st[s]=1;
			path[u]=s;
			if(dfs(u+1,depth))return 1;
			st[s]=0;
		}
	}
	return 0;
}
int main()
{
	path[0]=1;
	while(cin>>n&&n)
	{
		int dep=1;
		memset(st,0,sizeof(st));
		while(!dfs(1,dep))
		{
			dep++;
			
		}
		for(int i=0;i<dep;i++)
		{
			cout<<path[i]<<" ";
		}
		cout<<endl;
	}
    return 0;
}

IDA *

180. 排书

https://www.acwing.com/solution/content/161158/

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
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1010,N=31;
//char g[maxn][maxn];
int n;
int q[N],w[5][N];
int f()
{
	int res=0;
	for(int i=0;i+1<n;i++)
	{
		if(q[i+1]!=q[i]+1)
		{
			res++;
		}
	}
	return (res+2)/3;
	
}
bool check()
{
	for(int i=0;i<n;i++)
	{
		if(q[i]!=i+1)
			return false;
	}
	return true;
}
int dfs(int dep,int maxdep)
{
	if(dep+f()>maxdep)return 0;
	if(check())return 1;
	for(int l=0;l<n;l++)
	{
		for(int r=l;r<n;r++)
		{
			for(int k=r+1;k<n;k++)
			{
				memcpy(w[dep],q,sizeof(q));
				int x=0,y=0;
				for(x=r+1,y=l;x<=k;x++,y++)q[y]=w[dep][x];
				for(x=l;x<=r;x++,y++)q[y]=w[dep][x];
				if(dfs(dep+1,maxdep))return 1;
				memcpy(q,w[dep],sizeof(q));
			}
			
		}
	}
	return 0;
}
int main()
{
	int t=0;
	cin>>t;
	while(t--)
	{
		cin>>n;
		for(int i=0;i<n;i++)
		cin>>q[i];
		int dep=0;
		while(dep<5&&!dfs(0,dep))dep++;
		if(dep>=5)
		{
			cout<<"5 or more"<<endl;
		}
		else
		{
			cout<<dep<<endl;
		}
	} 
    return 0;
}

AcWing 181. 回转游戏

https://www.acwing.com/solution/content/4056/

image-20230728233423620

先A后F等于浪费了两次操作，剪枝opposite

op为每个调整的字母对映的位置

center为中间8个数的编号

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
85
86
87
88
89
90
91
92
93
94
95
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1010,N=24;
//char g[maxn][maxn];
int n;
int q[N];
int op[8][7] = {
    {0, 2, 6, 11, 15, 20, 22},
    {1, 3, 8, 12, 17, 21, 23},
    {10, 9, 8, 7, 6, 5, 4},
    {19, 18, 17, 16, 15, 14, 13},
    {23, 21, 17, 12, 8, 3, 1},
    {22, 20, 15, 11, 6, 2, 0},
    {13, 14, 15, 16, 17, 18, 19},
    {4, 5, 6, 7, 8, 9, 10}
};
int center[8] = {6, 7, 8, 11, 12, 15, 16, 17};
int opposite[8] = {5, 4, 7, 6, 1, 0, 3, 2};
int path[100];

int sum[4];
int f()
{
	memset(sum,0,sizeof(sum));
	for(int i=0;i<8;i++)
	{
		sum[q[center[i]]]++;
	}
	int s=0;
	for(int i=1;i<=3;i++)
	{
		s = max(s, sum[i]);
	}
	return 8-s;

}
bool check()
{
    for (int i = 1; i < 8; i ++ )
        if (q[center[i]] != q[center[0]])
            return false;
    return true;
}
void oper(int x)
{
	int t=q[op[x][0]];
	for(int i=0;i<6;i++)q[op[x][i]]=q[op[x][i+1]];
	
	q[op[x][6]] = t;
}
int dfs(int dep,int maxdep,int last)
{
	if(dep+f()>maxdep)return 0;
	if(!f())return 1;
	for(int i=0;i<8;i++)
	{
		if(opposite[i]==last)continue;
		oper(i);
		path[dep]=i;
		if(dfs(dep+1,maxdep,i))return 1;
		oper(opposite[i]);
	}
	return 0;
}
int main()
{
//	int t=0;
//	cin>>t;
	while(cin>>q[0]&&q[0])
	{
		
		for(int i=1;i<N;i++)
			cin>>q[i];
//		cout<<q[0];
		int dep=0;
		while(!dfs(0,dep,-1))dep++;
		if(!dep)
		{
			cout<<"No moves needed";
		}
		for(int i=0;i<dep;i++)
		 	printf("%c", 'A' + path[i]);
		cout<<endl;
		cout<<q[6]<<endl;
	} 
    return 0;
}

谷歌面试（BFS）

给一个m*n大小的矩阵表示地图，两辆车a，b，目的地分别是A，B，地图上用’‘表示道路，‘#’表示墙。

样例1：
a.A
###
b.B
结果：true
样例2:
aBAb
结果：false
样例3:
##.#
aBAb
结果：true

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <tuple>

using namespace std;

// 定义状态结构体
struct State {
    int ax, ay; // 车 a 的坐标
    int bx, by; // 车 b 的坐标
};

class Solution {
public:
    bool canReach(vector<string>& grid) {
        int m = grid.size();
        if (m == 0) return false;
        int n = grid[0].size();

        int startAx, startAy, startBx, startBy;
        int targetAx, targetAy, targetBx, targetBy;

        // 1. 解析地图，找到起点和终点
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 'a') {
                    startAx = i; startAy = j;
                    grid[i][j] = '.'; // 视为平地
                } else if (grid[i][j] == 'b') {
                    startBx = i; startBy = j;
                    grid[i][j] = '.';
                } else if (grid[i][j] == 'A') {
                    targetAx = i; targetAy = j;
                    grid[i][j] = '.';
                } else if (grid[i][j] == 'B') {
                    targetBx = i; targetBy = j;
                    grid[i][j] = '.';
                }
            }
        }

        // 2. BFS 初始化
        // visited[ax][ay][bx][by]
        // 既然是面试，用 vector vector 可能有点繁琐，可以用 flat index 或者多维 vector
        // 这里为了清晰使用多维 vector
        vector<vector<vector<vector<bool>>>> visited(
            m, vector<vector<vector<bool>>>(
                n, vector<vector<bool>>(
                    m, vector<bool>(n, false))));

        queue<State> q;
        q.push({startAx, startAy, startBx, startBy});
        visited[startAx][startAy][startBx][startBy] = true;

        int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        while (!q.empty()) {
            State curr = q.front();
            q.pop();

            // 检查是否到达目标
            if (curr.ax == targetAx && curr.ay == targetAy &&
                curr.bx == targetBx && curr.by == targetBy) {
                return true;
            }

            // 策略：尝试移动车 a
            for (auto& d : dirs) {
                int nax = curr.ax + d[0];
                int nay = curr.ay + d[1];

                // 检查边界和墙
                if (nax >= 0 && nax < m && nay >= 0 && nay < n && grid[nax][nay] != '#') {
                    // 关键检查：a 移动后的位置不能是 b 当前的位置
                    if (!(nax == curr.bx && nay == curr.by)) {
                        if (!visited[nax][nay][curr.bx][curr.by]) {
                            visited[nax][nay][curr.bx][curr.by] = true;
                            q.push({nax, nay, curr.bx, curr.by});
                        }
                    }
                }
            }

            // 策略：尝试移动车 b
            for (auto& d : dirs) {
                int nbx = curr.bx + d[0];
                int nby = curr.by + d[1];

                // 检查边界和墙
                if (nbx >= 0 && nbx < m && nby >= 0 && nby < n && grid[nbx][nby] != '#') {
                    // 关键检查：b 移动后的位置不能是 a 当前的位置
                    if (!(nbx == curr.ax && nby == curr.ay)) {
                        if (!visited[curr.ax][curr.ay][nbx][nby]) {
                            visited[curr.ax][curr.ay][nbx][nby] = true;
                            q.push({curr.ax, curr.ay, nbx, nby});
                        }
                    }
                }
            }
        }

        return false;
    }
};

// 测试代码
int main() {
    Solution sol;
    
    // 样例 2: 狭窄通道，无法交换
    vector<string> grid1 = {
        "aBAb" 
    };
    cout << "Example 2 (Expected 0): " << sol.canReach(grid1) << endl;

    // 样例 3: 有避让空间
    vector<string> grid2 = {
        "##.#",
        "aBAb"
    };
    cout << "Example 3 (Expected 1): " << sol.canReach(grid2) << endl;

    return 0;
}

发表于 更新于 分类于
这里有东西被加密了，需要输入密码查看哦。
阅读全文 »

发表于 更新于 分类于

问题背景

促销在电子商务平台的营销工作中起着关键作用。他们通过为客户提供更多的价值，从而显著提升了销售额。向客户提供优惠(如图1所示)会产生完成预订的动机，并推动业务增长。在增加购买可能性的同时，如果促销活动时的销售净收入小于不提供促销活动时的净收入，促销活动也可能招致增量货币损失。通常，会制定专门的预算来弥补这一增加的净收入损失，以确保可持续的竞选活动。

预算约束营销最近越来越受欢迎，尤其是在促销分配方面。许多解决方案考虑一个恒定的成本因素[18]。然而，在存在因果增量估计的情况下，晋升的货币影响可能导致不同的、积极的或消极的结果。现有的解决方案主要依赖于基于意图的模型，不能适应因果模型的负值，因此不适用于此类问题。

本文利用提升模型(uplift modeling)的因果估计，形式化了预算约束下的多选择晋升分配问题。我们提出了一种新的在线选择背包设置中负值和权重的解决方案。我们在最大的在线旅游平台之一Booking.com上展示了该方法的部署，并在现实生活的实验研究中对其进行了各种基准测试。

我们的主要贡献有:

  1. 将预算约束下的促销个性化问题表述为具有因果估计的在线mckp。
  2. 基于因果隆起模型估计和多项选择背包优化的两步求解方法。
  3. Online-MCKP解的新颖扩展，以适应负值和权值。
  4. 在Booking.com平台进行大规模的真实促销活动实验研究。

解决方法

符号定义

𝑌𝑖 - a binary random variable representing a completion of a purchase

​ 一个二进制随机变量，表示购买完成

𝑅𝑖 - a continuous random variable representing the net monetary revenue associated with the purchase (sum of all revenues minus all promotional costs)

​ 表示与购买相关的净货币收入的连续随机变量（所有收入的总和减去所有促销成本）

𝑌𝑖 (𝑘): potential purchase 对于客户𝑖 和促销𝑘如果客户𝑖 获得促销𝑘

𝑅𝑖 (𝑘): potential net revenue表示如果客户𝑖 获得促销𝑘.

k=0, no promotion
$$
CATE_{𝑌} (𝑖, 𝑘) = E(𝑌_{𝑖} (𝑘) − 𝑌_{𝑖} (0) | 𝑋 = 𝑥𝑖 )
$$

表示如果促销k，则对客户i的预期购买概率的增量影响

$$
CATE_{𝑅} (𝑖, 𝑘) = E(𝑅_{𝑖}(𝑘) − 𝑅_{𝑖}(0) | 𝑋 = 𝑥𝑖 )
$$

ppt66-68

CATEL (𝑖, 𝑘) = −CATE𝑅 (𝑖, 𝑘)

𝑣𝑖𝑘 is CATE𝑌 (𝑖, 𝑘)and 𝑤𝑖𝑘 is CATEL (𝑖, 𝑘)

MCKP：给你N组物品，然后每一组你至多选择一个物品,每个物品都有自己的体积和价值，现在给你一个容里为M的背包，让你用这个背包装物品，使得物品价值总和最大

这里一个人是一组，K1,K2….

每个人可能收到的优惠券k∈Ki,k=0表示这个用户没有优惠

image-20231029224008191

屏幕截图 2023-10-29 224151

解决方案框架

zaiwen.top2023_10_29 23_01_58

先调了公共的UpliftML package，Optimization部分

Dominant items

删除Dominant和 LP-Dominant，和The Multiple-Choice Knapsack Problem这篇一样

image-20231029230943979

Incremental value and weight

image-20231029231056168.png

感觉和mckp那篇也差不多

此外，the incremental efficiency 𝑣𝑖𝑑/𝑤𝑖𝑑 is monotonically decreasing with 𝑑，除了d=0到d=1，可能w和v是负的，看图3。

Efficiency angle

image-20231029231331394.png

Efficiency angle threshold

1: Input:

• Set of past dominant items 𝑃

• Knapsack capacity 𝐶

• Current customer index 𝑖

• Expected number of customers |𝑈 |

2: Sort 𝑃 by decreasing angle 𝜃𝑝

3: for 𝑝 ∈ 𝑃 do:

4: if p=0:
$$
𝑓 ((𝜃_{0}) ) = w_{0}/|𝑃 |
$$

5: else:
$$
𝑓 ((𝜃_{p}) ) = 𝑓 (𝜃_{p} −1 ) + 𝑤_{p} /|𝑃 |
$$

6: end for

7: Return efficiency threshold 𝜃^{*}:
$$
𝜃^{ * } ← 𝑚𝑖𝑛_{𝑝∈𝑃} ({ 𝜃_{p} | 𝑓 (𝜃_{p} ) ≤ 𝐶/(|𝑃 |/𝑖 · (|𝑈 |−𝑖+1) )})
$$
// TODO：这个就不知道咋想出来的，问问去

总的：O (|𝐾𝑖 | · 𝑙𝑜𝑔|𝐾𝑖 |)，𝜃更新具有O(|𝑈 |) 复杂性

系统架构

比较了好几种optimization，global，local， Greedy，下面几个

  1. Online MCKP (On-MCKP):
    • 情境描述：该方法对应于真实世界中的情景，其中顾客逐一到达，每次决策都必须在特定时间步骤中做出，即每到一个新顾客就需要做出促销活动的决策。
    • 信息限制：在开始时，没有有关一般权重和价值分布的信息。
    • 决策过程：方法会根据剩余预算和更新的效率角度函数（Algorithm 2描述）来调整促销活动的分配决策。
  2. Offline MCKP (Off-MCKP):
    • 情境描述：与Online MCKP相比，这种方法不同的是提前知道所有物品，即所有的顾客和可能的促销活动。
    • 信息利用：因为提前知道所有物品，可以在分配决策之前仅适应一次效率角度函数（Algorithm 1描述）。
    • 决策过程：在知道所有顾客和促销活动之后，算法会决定为每个顾客提供哪种促销活动，而不需要更新效率角度函数。

在这两种方法中，主要的区别在于信息利用和决策时机。Online MCKP需要在每个时间步骤中动态地做出决策，而Offline MCKP可以提前知道所有信息，然后在不需要动态更新的情况下做出决策。

  1. Integer Linear Programming (ILP)
    • 解决方法：ILP求解器用于在离线设置中寻找最优的上界解决方案。
    • 线性规划：MCKP问题可以被表示为一个线性规划，并且采用了论文中所描述的线性方程（Equation 1）来解决。
    • 预算常数：预算常数 C被设置为零（C=0）。
    • 工具和求解器：研究使用了 Python PuLP 软件包和 CBC（Coinor branch and cut）求解器。整体求解器运行时间被限制在3小时内。
    • 性能说明：尽管对于背包问题有更合适的求解器，研究中仅遇到了一个实例，即在有限的运行时间内无法达到最优解。不过，它达到了一个可行解，且具有微小的最优性差距。

ILP方法利用了数学规划中的整数线性规划来解决MCKP问题。在离线设置下，ILP被用来找到一个最优的上界解决方案，其依赖于线性规划的建模，并使用了特定的求解器和工具来解决问题。

结论

这部分感觉看原文，比较了这几个方法比ILP垃圾多少（不是），然后是看online-mckp自己的一个性质：bound，然后three flat-discount levels 看ROI，最后是一个净利润和阈值的浮动（？

0%