第一部分 前八章

该部分笔记记录书上的解释及例子

第一章 食用须知

1.没有啥实质性内容,一些开始这本书前的建议

第二章 C/C++入门知识

**1.**也没有啥用,零基础的可以看看,有基础的直接跳过就行了

**2.**唯一注意点的只有输出格式,这个用的少可能会忘记(

**3.**以及math库中的函数

**4.**memset或fill

**5.**浮点数的比较

**6.**圆周率

1
const double Pi = acos(-1.0);

**7.**复杂度

第三章 入门篇(1) —– 入门模拟

**1.**简单模拟

  1. PAT B 1001

    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
    #include <iostream>

    int main()
    {
        int n;
        std::cin >> n;
        int count = 0;

        while (n!=1)
        {
            if (n%2==0)
            {
                n /= 2;
                count++;
            }
            else
            {
                n = (3 * n + 1) / 2;
                count++;
            }
        }

        std::cout << count << std::endl;

        system("pause");
        return 0;
    }

  2. PAT B 1032

    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
    #include <iostream>

    //注意此处,段错误的原因 可能由于测试数据较,超过了数组的范围
    const int maxn = 100010;
    int school[maxn] = {0};

    int main()
    {
        int n, ID, score;
        std::cin >> n;

        int k = 1, MAX = -1;

        for (int i = 1; i <= n;i++)
        {
            std::cin >> ID >> score;
            school[ID] += score;

            if (school[ID]>MAX)
            {
                MAX = school[ID];
                k = ID;
            }
        }

        std::cout << k << " " << MAX << std::endl;
        return 0;
    }

**2.**查找元素

  1. codeup 1934

    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
    #include <iostream>

    int num[200] = {0};

    int main()
    {
        int n;
        std::cin >> n;

        for (int i = 1; i <= n;i++)
            std::cin >> num[i];

        //待查询的数
        int k, flag = 1;
        std::cin >> k;

        for (int i = 1; i <= n;i++)
        {
            if (num[i]==k)
            {
                std::cout << i << std::endl;
                flag = 0;
                break;
            }
        }

        if (flag)
            std::cout << "-1" << std::endl;

        system("pause");
        return 0;
    }

**3.**图形输出

  1. PAT B 1036

    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
    #include <iostream>

    int main()
    {

        int n, col;
        char s;
        std::cin >> n >> s;
        //根据奇数还是偶数计算行数
        if (n%2==0)
            col = n / 2;
        else
            col = n / 2 + 1;

        for (int i = 1; i <= col;i++)
        {
            //单独处理第一行和最后一行
            if (i==1 || i==col)
            {
                for (int i = 1; i <= n;i++)
                    std::cout << s;
                std::cout << std::endl;
            }
            else
            {
                for (int i = 1; i <= n;i++)
                {
                    if (i==1 || i==n)
                        std::cout << s;
                    else
                        std::cout << " ";
                }
                std::cout << std::endl;
            }
        }

        return 0;
    }

**4.**日期处理

  1. codeup 1928

    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
    //思路:一天天的累加,

    #include <iostream>

    int month[13][2] = {{0, 0}, {31, 31}, {28, 29}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}, {31, 31}, {30, 30}, {31, 31}, {30, 30}, {31, 31}};
    bool isLeap(int year)
    {
        return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
    }

    int main()
    {
        int time1, y1, m1, d1;
        int time2, y2, m2, d2;
        while (std::cin >> time1 >> time2)
        {
            if (time1 > time2)
            {
                int temp = time1;
                time1 = time2;
                time2 = temp;
            }

            int ans = 1;
            y1 = time1 / 10000, m1 = time1 % 10000 / 100, d1 = time1 % 100;
            y2 = time2 / 10000, m2 = time2 % 10000 / 100, d2 = time2 % 100;

            while (y1<y2 || m1<m2 || d1<d2)
            {
                d1++;
                if (d1==month[m1][isLeap(y1)]+1)
                {
                    m1++;
                    d1 = 1;
                }
                if (m1==13)
                {
                    y1++;
                    m1 = 1;
                }
                ans++;
            }
            std::cout << ans << std::endl;
        }
        return 0;
    }

**5.**进制转换

  1. PATB1022

    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
    #include <iostream>
    #include <stack>

    //测试用例有一个错误
    void transform(std::stack<int>& array,int n,int base)
    {
        int num[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        while (n!=0)
        {
            array.push(num[n % base]);
            n /= base;
        }
    }

    int main()
    {
        std::stack<int> array;
        int a, b,sum,_system;
        std::cin >> a >> b >> _system;
        sum = a + b;

        transform(array, sum, _system);
        while (!array.empty())
        {
            std::cout << array.top();
            array.pop();
        }
        std::cout << std::endl;

        //system("pause");
        return 0;
    }

**6.**字符串处理

  1. codeup5901

    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
    //思路 二分,从两边同时进行比较
    //没有找到codeup的网站,测试用例可能不全
    #include <iostream>
    #include <string>

    int main()
    {
        std::string str;
        
        while (std::cin >> str)
        {
        int len = str.size();
        int flag = 0;

        for (int i = 0, j = len - 1; i < j;i++,j--)
        {
            if (str[i]!=str[j])
                flag = 1;
        }
        if (flag)
            std::cout << "NO" << std::endl;
        else
            std::cout << "YES" << std::endl;
        }
        system("pause");
        return 0;
    }

  2. PATB1009

    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
    #include <iostream>
    #include <string>
    #include <stack>
    #include <sstream>

    //本题主要难点在于处理字符串,根据空格分割成一个个字符串,再反过来输出
    //我的解题思路 使用内核格式化(好像叫这个,不是很清楚,但是之前没用过,在这里想起来了,于是用到)
    //进行分割,将分割的字符串入栈

    int main()
    {
        std::string str;
        std::getline(std::cin, str);
        std::stack<std::string> array;

        std::stringstream input(str);
        std::string temp;
        while (input >> temp)
            array.push(temp);
        
        while (!array.empty())
        {
            std::cout << array.top();
            array.pop();
            if (!array.empty())
                std::cout << " ";
        }
        std::cout << std::endl;

        system("pause");
        return 0;
    }

第四章 入门篇(2) —- 算法初步

一.排序
**1.**选择排序

最简单的排序方法,就是每次用当前元素,跟后面的所有元素挨个比较,若后面的更大/更小,则换位置，或者采用记录下标,换下标,后续再进行一次交换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void selectSort()
{
    for (int i=1; i <=n; i++)
    {
        int k = i;     //挑选最小元素的下标
        for (int j=i; j<=n; j++)
        {
            if (A[j] < A[k])
                k = j;
        }
    }
    //交换
    int temp = A[i];
    A[i] = A[k];
    A[k] = temp;
}
**2.**插入排序

插入排序也是最简单排序方式之一,实现原理为,(假设数组下标从0开始),从1开始比较,每次将当前元素与前一个元素比较,若小于/大于,则把该插入的位置下标向前移动,直至不符合比较条件,则插入,过程是左边一直有序,整体逐渐有序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void insertSort()
{
    //书中是数组元素从1开始,个人习惯从0开始,细节上会和书上有点区别
    for (int i=1; i<n; i++)
    {
        //temp存储当前插入元素,因为给其腾位置时,他本来的位置会被覆盖,j为temp应插入的位置
        int temp = A[i], j=i;
        //从j开始向前寻找,j>0表示j最多只能到达0下标,防止越界
        while (j>0 && temp<A[j-1])
        {
            A[j] = A[j-1];
            j--;
        }
        //插入
        A[j] = temp;
    }
}
**3.**排序题与sort函数的应用

  1. PATA1025

    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
    #include <iostream>
    #include <algorithm>
    #include <string>

    //主要熟悉了对sort函数的使用,比较器的添加,本体的思路不难,就是细节上需要稍微注意点,不同部分
    //数组防止重叠

    struct Student
    {
        std::string id;
        int score;
        int location;
        int local_rank;
    } stu[30010];

    //sort 比较器的设置
    bool cmp(Student a,Student b)
    {
        if (a.score != b.score)
            return a.score > b.score;
        else
            return a.id < b.id;
    }

    int main()
    {
        int n,num=0;
        std::cin >> n;

        for (int i = 1; i <= n; i++)
        {
            int k;
            std::cin >> k;
            num += k;

            for (int j = num-k; j < num; j++)
            {
                std::cin >> stu[j].id >> stu[j].score;
                stu[j].location = i;
            }
            //思路先对该部分排序
            std::sort(stu + num - k, stu + num, cmp);
            //再对该部分计算本地rank
            stu[num - k].local_rank = 1;
            for (int j = num - k + 1,r=2; j < num;j++,r++)
            {
                if (stu[j].score == stu[j-1].score)
                    stu[j].local_rank = stu[j - 1].local_rank;
                else
                {
                    stu[j].local_rank = r;
                }
            }
        }
        std::cout <<num << std::endl;
        //对全体部分排序
        std::sort(stu, stu + num, cmp);
        //挨个输出
        int r = 1;
        for (int i = 0; i < num;i++)
        {
            if (i>0 && stu[i].score!=stu[i-1].score)
                r=i+1;
            std::cout << stu[i].id << " " << r << " " << stu[i].location << " " << stu[i].local_rank << std::endl;
        }


        return 0;
    }
二.散列
1.散列的定义与整数散列

一个简单的情况,给出N个整数,再给出M个整数,问这M个数中的N个数是否再N个数中出现过,最直观的解决方法就是,每次取出M中一个数,一个一个试,这样的时间复杂度O(MN),很大,散列属于是空间换时间,下面给个例子品鉴一下

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
//此为找是否出现,所有hashTable的类型为bool
#include <iostream>

const int maxn = 100010;
bool hashTable[maxn] = {false};

int main()
{
    int n, m, x;

    std::cin >> n >> m;

    for (int i = 0; i < n;i++)
    {
        std::cin >> x;
        hashTable[x] = true;     //出现过就记录为true
    }

    for (int i = 0; i < m;i++)
    {
        std::cin >> x;
        if (hashTable[x]==true)
            std::cout << "yes" << std::endl;
        else
            std::cout << "no" << std::endl;
    }

    return 0;
}
//出现次数 基本思路一致,hashTable的类型改为int
#include <iostream>
const int maxn = 100010;
int hashTable[maxn] = {0};

int main()
{
    int n, m, x;

    std::cin >> n >> m;

    for (int i = 0; i < n;i++)
    {
        std::cin >> x;
        hashTable[x]++;
    }

    for (int i = 0; i < m;i++)
    {
        std::cin >> x;
        std::cout << hashTable[x] << std::endl;
    }

    return 0;
}

散列一句话来说就是**”将元素通过一个函数转换成整数,使得该整数可以尽量唯一地代表这个元素”,转换函数称为散列函数 H**,也就是说元素在转换前为key,转换后就是H(key)

对于key是整数的情况来说,常用的散列函数有,直接定址法,平方取中法,除留余数法,上述用数组下标来处理就是直接定址法,也是最常用的散列应用,另一个实用且常用的就是除留余数法

​ H(key) = key%mod

很容易发现,可能会出现两个不同的数key1和key2，它们的hash值相同,但key1已经把H(key1)的位置占据了,key2便不能使用这个位置,这种情况叫做**”冲突”**,下面有三种方式来解决,提一下,但不过度赘述了

  1. 线性探查法
  2. 平方探查法
  3. 链地址法
2.字符串hash初步
三.递归
1.分治

主要三个步骤 1.划分为若干小问题 2.解决子问题 3.合并

比较明显的一个经典问题 Fibonacci 求解

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
//全排列
#include <iostream>
using namespace std;

const int maxn = 11;

int n, P[maxn], hashTable[maxn] = {false};

void get(int index)
{
    if (index == n+1)
    {
        for (int i = 1; i <= n;i++)
        {
            cout << P[i];
        }
        cout << endl;
        return;
    }
    //划分从三个子问题出发
    for (int x = 1; x <= n;x++)
    {
        if (hashTable[x]==false)
        {
            P[index] = x;
            hashTable[x] = true;
            get(index + 1);
            hashTable[x] = false;
        }
    }
}

int main()
{
    cin >> n;
    get(1);

    system("pause");
    return 0;
}

另一个例子就是n皇后问题,同时用到了上述全排列

image-20220427091416531

思路是对于这样的n列n行的棋盘,按从1-n列的顺序记录它们的行列,因为每个皇后不能在同一列或同一行,就不用考虑他们在同一列的问题了,所以每列只能有一个皇后,所以a方案记录为24135,b方案记录为35142,再根据排列方案判断是否不在同一对角线,也就是说对于行列上的判断,已经通过全排列解决了

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
#include <iostream>
#include <cmath>
using namespace std;

int count = 0;
int n;
int p[11];
bool hashTable[11] = {false};

void get(int index)
{
    if (index == n+1)
    {
        //生成一个排列
        bool flag = true;
        //判断排列是否符号条件
        for (int i = 1; i <= n;i++)
        {
            for (int j = i + 1; j <= n;j++)
            {
                //行列差如果相等则在同一对角线
                if (abs(i-j)==abs(p[i]-p[j]))
                    flag = false;
            }
        }
        if (flag)
            count++;
    }
    for (int x = 1; x <= n;x++)
    {
        if (hashTable[x]==false)
        {
            p[index]=x;
            hashTable[x] = true;
            get(index + 1);
            hashTable[x] = false;
        }
    }
}



int main()
{
    cin >> n;
    get(1);

    cout << count << endl;

    system("pause");
    return 0;
}

上述方案枚举了所有可能性,但可以想到其中有些方案在前面就已经冲突,如b方案1 3列的皇后已经冲突了,后续的比较与排列都是无意义的,这时可以采用另一种方法,回溯,再冲突时直接回溯,不进入子方案搜寻

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
#include <iostream>
#include <cmath>
using namespace std;

int count = 0;
int n;
bool hashTable[11] = {false};
int p[11];

void get(int index)
{
    if (index == n+1)
    {
        count++;
        return;
    }
    for (int x = 1; x <= n;x++)
    {
        if (hashTable[x]==false)
        {
            bool flag = true;
            //pre 和 index 为列 , x为index的行,还没写入p中,先判断,
            //index列 与 前面列的是否冲突 p[pre]为pre的行
            for (int pre = 1; pre < index;pre++)
            {
                if (abs(index-pre)==abs(x-p[pre]))
                {
                    flag = false;
                    break;
                }
            }
            //若已经冲突,不继续递归,直接回溯
            if (flag)
            {
                p[index] = x;
                hashTable[x] = true;
                get(index + 1);
                hashTable[x] = false;
            }
        }
    }
}

int main()
{
    cin >> n;
    get(1);
    cout << count << endl;

    system("pause");
    return 0;
}
四.贪心
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
//PATB1020 
#include <cstdio>
#include <cstdlib>
#include <algorithm>
using namespace std;

struct mooncake
{
    double store;
    double sell;
    double price;
} cake[1010];

bool cmp(mooncake a,mooncake b)
{
    return a.price > b.price;
}

int main()
{
    int n;
    double D;
    scanf("%d%lf", &n, &D);

    for (int i = 0; i < n;i++)
    {
        scanf("%lf", &cake[i].store);
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%lf", &cake[i].sell);
        cake[i].price = cake[i].sell / cake[i].store;
    }
    sort(cake, cake + n, cmp);
    double ans = 0;
    for (int i = 0; i < n;i++)
    {
        if (cake[i].store <=D)
        {
            D -= cake[i].store;
            ans += cake[i].sell;
        }else
        {
            ans += cake[i].price * D;
            break;
        }
    }
    printf("%.2f\n", ans);

    system("pause");
    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
#include <iostream>

int count[10];

int main()
{
    for (int i = 0; i < 10;i++)
        std::cin >> count[i];

    for (int i = 1; i < 10;i++)
    {
        if (count[i]>0)
        {
            std::cout << i;
            count[i]--;
            break;
        }
    }
    for (int i = 0; i < 10;i++)
    {
        while (count[i]!=0)
        {
            std::cout << i;
            count[i]--;
        }
    }
    std::cout << std::endl;

    system("pause");
    return 0;
}
2.区间贪心

image-20220428093219231

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
#include <iostream>
#include <algorithm>
using namespace std;

struct section
{
    int flag = 0;//判断是否被选中 
    int x;       //左端点
    int y;       //右端点
} sec[20];

//思路: 1.优先选左端点最大的 2.如左端点相等,选右端点小的

//反之,选右端点最小的同行也行,思路类似

bool cmp(section a,section b)
{
    if (a.x != b.x)
        return a.x > b.x;
    else
        return a.y < b.y;
}

int main()
{
    int n;
    cin >> n;

    for (int i = 0; i < n;i++)
    {
        cin >> sec[i].x >> sec[i].y;
    }

    sort(sec, sec + n, cmp);

    sec[0].flag = 1;
    int get_x = sec[0].x;      //向下遍历,逐个加入

    for (int i = 1; i < n;i++)
    {
        if (sec[i].y<=get_x)
        {
            get_x = sec[i].x;
            sec[i].flag = 1;
        }
    }

    for (int i = 0; i < n;i++)
    {
        if (sec[i].flag)
        {
            cout << "(" << sec[i].x << "," << sec[i].y << ")"
                 << " ";
        }
    }
    cout << endl;

    system("pause");
    return 0;
}

这是选区间不相交问题,还有一种区间选点问题,与之类似,很容易想到,只要找不相交的区间就行了,不相交的区间数等于点数,即把sec[i].y<=get_x 改为 sec[i].y < get_x 即可

五.二分
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
#include <iostream>
#include <vector>
#include <string>

std::string search(std::vector<int>& array,int data)
{
    int left = 0;
    int right = array.size() - 1;

    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (array[mid] == data)
        {
            return "YES";
        }
        else if (array[mid] > data)
        {
            right = mid - 1;
        }
        else
            left = mid + 1;
    }
    return "NO";
}

int main()
{
    int n;
    std::cin >> n;
    int data;
    std::vector<int> array;
    for (int i = 0; i < n;i++)
    {
        std::cin >> data;
        array.push_back(data);
    }

    int m;
    std::cin >> m;
    for (int i = 0; i < m;i++)
    {
        std::cin >> data;
        std::cout << search(array, data) << std::endl;
    }
    system("pause");
    return 0;
}
2.二分法拓展

求根号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
#include <iostream>
#include <cmath>

const double PI = std::acos(-1.0);
const double eps = 1e-5;

double f(double R,double h)
{
    double alpha = 2 * std::acos((R - h) / R);
    double L = 2 * std::sqrt(R * R - (R - h) * (R - h));
    double s1 = alpha * R * R / 2 - L * (R - h) / 2;
    double s2 = PI * R * R / 2;
    return s1 / s2;
}

double solve(double R,double r)
{
    double left = 0, right = R, mid;
    while (right - left > eps)
    {
        mid = (left + right) / 2;
        if (f(R,mid)>r)
        {
            right = mid;
        }
        else
        {
            left = mid;
        }
    }
    return mid;
}

int main()
{
    double R, r;
    std::cin >> R >> r;
    std::cout << solve(R, r);
    return 0;
}
3.快速幂
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//a b m 求 a ^ b & m
#include <iostream>

using LL = long long;

LL binaryPow(LL a,LL b,LL m)
{
    if (b == 0)
        return 1;
    if (b%2 == 1)
        return a * binaryPow(a, b - 1, m) % m;
    else
    {
        LL mu1 = binaryPow(a, b / 2, m);
        return mu1 * mu1 % m;
    }
}

int main()
{
    return 0;
}
六.two_pointer
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
std::vector<int> array{66, 12, 33, 57, 64, 27, 18};

void merge(int left1,int right1,int left2,int right2)
{
    std::vector<int> temp;
    int i = left1, j = left2, index = 0;
    while (i<=right1 && j <= right2)
    {
        if (array[i] <= array[j])
        {
            temp.push_back(array[i++]);
            index++;
        }
        else
        {
            temp.push_back(array[j++]);
            index++;
        }
    }
    while (i<=right1)
    {
        temp.push_back(array[i++]);
        index++;
    }
    while (j<=right2)
    {
        temp.push_back(array[j++]);
        index++;
    }

    for (int i = 0; i < index;i++)
    {
        array[left1++] = temp[i];
    }
}

void merge_sort(int left,int right)
{
    if (left<right)
    {
        int mid = (left + right) / 2;
        merge_sort(left, mid);
        merge_sort(mid + 1, right);
        merge(left, mid, mid + 1, right);
    }
}


int main()
{
    merge_sort(0, 6);
    for (int i = 0; i < 7;i++)
        std::cout << array[i] << " ";
    system("pause");
    return 0;
}

非递归的思路也差不多,非递归的版本,设定了一个step步长,也就是每次合并时元素的个数,比如第一轮是2,第二轮就是4,直到step/2 < n 也就是左区间的元素个数在总个数之内才能归并

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
//归并排序 非递归版本
#include <iostream>
#include <vector>
#include <algorithm>

std::vector<int> array{66, 12, 33, 57, 64, 27, 18};

void merge(int left1, int right1,int left2, int right2)
{
    std::vector<int> temp;
    int i = left1, j = left2, index = 0;

    while (i<=right1 && j<=right2)
    {
        if (array[i] <= array[j])
        {
            temp.push_back(array[i++]);
            index++;
        }
        else
        {
            temp.push_back(array[j++]);
            index++;
        }
    }

    while (i<=right1)
    {
        temp.push_back(array[i++]);
        index++;
    }
    while (j<=right2)
    {
        temp.push_back(array[j++]);
        index++;
    }
    for (int i = 0; i < index;i++)
        array[left1++] = temp[i];
}


// void merge_sort(int n=7)
// {
//     for (int step = 2; step/2 < n;step*=2)
//     {
//         for (int i = 0; i < n;i+=step)
//         {
//             int mid = i + step / 2 - 1;
//             if (mid+1 < n)
//             {
//                 merge(i, mid, mid + 1, std::min(i+step-1,n-1));
//             }
//         }
//     }
// }

void merge_sort(int n=7)
{
    for (int step = 2; step / 2 < n;step*=2)
    {
        for (int i = 0; i < n;i+=step)
        {
            std::sort(array.begin() + i, array.begin() + std::min(i + step , n));
        }
    }
}


int main()
{
     merge_sort();
    for (auto i : array)
    {
        std::cout << i << " ";
    }
    system("pause");
    return 0;
}
//可以采用sort的函数来进行合并,这样思路会更清晰,就是将step长度的小区间分割排序
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
#include <iostream>
#include <vector>
#include <ctime>

std::vector<int> array{35, 18, 16, 72, 24, 65, 12, 88, 46, 28, 55};


int core(int left,int right)
{
    int p = rand() % (right - left + 1) + left;
    std::swap(array[p], array[left]);
    int temp = array[left];

    while (left < right)
    {
        while (left < right && array[right] > temp)
            right--;
        array[left] = array[right];
        while (left<right && array[left] < temp)
            left++;
        array[right] = array[left];
    }
    array[left] = temp;
    return left;
}

void QuickSort(int left,int right)
{
    if (left < right)
    {
        int pos = core(left,right);
        QuickSort(left, pos);
        QuickSort(pos + 1, right);
    }
}

int main()
{
    std::srand(std::time(NULL));
    QuickSort(0, 10);

    for (auto i : array)
        std::cout << i << " ";

    std::cout << std::endl;

     system("pause");
    return 0;
}
七.其他高效技巧与算法
1.打表

懂得都懂

2.活用递推

就是找规律吧

3.随机选择算法

简单来说就是快速排序的思想

第五章 入门篇(3) —- 数学问题

一.简单数学

就是简单的数学逻辑,应用到部分题上

二.最大公约数与最小公倍数

  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
    //辗转相除法 根据定理 gcd(a,b) = gcd(b,a%b) 实现, 证明没太看懂还

    //1.递归
    int gcd(int a, int b)
    {
        if (b == 0)
            return a;
        return gcd(b,a%b);
    }

    //2.迭代
    int gcd(int a,int b)
    {
        int r;
        if (a < b)
            swap(a,b);
        while (b)
        {
            r = a%b;
            a = b;
            b = r;
        }
        return a;
    }

  2. 最小公倍数

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //是由最大公约数得到的 在求得最大公约数d后, a*b/d即可

    int lcm(int a,int b)
    {
        int i = a, j = b,r;
        if (a<b)
            std::swap(a, b);
        while (b)
        {
            r = a % b;
            a = b;
            b = r;
        }
        return i/a*j;
    }
三. 分数的四则运算

注意化简就行

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 <iostream>
#include <algorithm>
struct Fraction
{
    int up, down;
};

int gcd(int a,int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

Fraction reduction(Fraction result)
{
    if (result.down < 0)
    {
        result.up = -result.up;
        result.down = -result.down;
    }
    if (result.up == 0)
        result.down = 1;
    else
    {
        int d = gcd(std::abs(result.up), std::abs(result.down));
        result.up /= d;
        result.down /= d;
    }
    return result;
}

Fraction add(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.down + f2.up * f1.down;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction minu(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.down - f1.down * f2.up;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction multi(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.up;
    result.down = f1.down * f2.down;
    return reduction(result);
}

Fraction divide(Fraction f1,Fraction f2)
{
    Fraction result;
    result.up = f1.up * f2.down;
    result.down = f1.down * f2.up;
    return reduction(result);
}

void showResult(Fraction r)
{
    r = reduction(r);
    if (r.down == 1)
        printf("%lld", r.up);
    else if (std::abs(r.up) > r.down)
        printf("%d %d/%d", r.up / r.down, std::abs(r.up) % r.down, r.down);
    else
        printf("%d/%d", r.up, r.down);
}

int main()
{
    std::cout << "hello, world" << std::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
#include <iostream>
#include <type_traits>
#include <vector>

using MAX = std::integral_constant<int, 10001>::type;
using GET = std::integral_constant<int, 1500>::type;


std::vector<int> prime;
int num = 0;

bool p[MAX::value]{false};

void Find_Prime()
{
    for (int i = 2; i < MAX::value;i++)
    {
        if (p[i] == false)
        {
            prime.push_back(i);
            for (int j = i + i; j < MAX::value;j+=i)
                p[j] = true;
        }
    }
}

int main()
{
    Find_Prime();
    int n;
    while (std::cin >> n)
    {
        std::cout << prime[n - 1] << std::endl;
    }
    return 0;
}

五.质因子分解

思路就是先求得一个质数表,然后从质数表最小的开始枚举,用n除以该质数,直到不能整除,然后除下一个质数，如果最后枚举完,n还不为1,说明n本身也是质数了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include <iostream>
#include <cmath>
#include <type_traits>
#include <vector>

using MAX = std::integral_constant<int, 10000>::type;

int prime[MAX::value], num = 0;
bool p[MAX::value]{false};

void Find_Prime()
{
    for (int i = 2; i < MAX::value;i++)
    {
        if (p[i] == false)
        {
            prime[num++] = i;
            for (int j = i + i; j < MAX::value;j+=i)
                p[j] = true;
        }
    }
}

struct factor
{
    int count;
    int cnt;
};

std::vector<factor> Factor;

int main()
{
    int n, pos = 0;
    std::cin >> n;
    Find_Prime();
    int sqr = (int)std::sqrt(1.0 * n);

    for (int i = 0; i < num && i <= sqr;i++)
    {
        if (n % prime[i] == 0)
        {
            Factor.push_back({0, prime[i]});
            while (n%prime[i] == 0)
            {
                Factor[pos].count++;
                n /= prime[i];
            }
            pos++;
        }
        if (n == 1)
            break;
    }
    if (n != 1)
        Factor.push_back({1, n});

    int sum = 0;

    for (auto i : Factor)
    {
        if (sum > 0)
            std::cout << "*";
        std::cout << i.cnt;
        if (i.count > 1)
            std::cout << "^" << i.count;
        sum++;
    }

    system("pause");
    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
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
#include <iostream>
#include <algorithm>
#include <type_traits>
#include <string>

using MAX = std::integral_constant<int, 100>::type;


//大数四则运算基本算法 除乘法外其他本质都是小学数学
struct Big_Num
{
    int d[MAX::value];
    int length;
    Big_Num()
    {
        length = 0;
        std::fill(d, d + MAX::value, 0);
    }
};

void transform(Big_Num& temp,std::string& str)
{
    int len = (int)str.size();

    for (int i = 0; i < len;i++)
    {
        temp.d[i] = str[len - i - 1]-'0';
    }

    temp.length = len;
}

int compare(Big_Num& a,Big_Num& b)
{
    if (a.length != b.length)
        return a.length > b.length;
    int len = (int)a.length;

    for (int i = len - 1; i >= 0;i--)
    {
        if (a.d[i] > b.d[i])
            return 1;
        else if (a.d[i] < b.d[i])
            return 0;
    }
    return -1;
}

Big_Num add(Big_Num& a, Big_Num& b)
{
    Big_Num c;
    int carry = 0;
    for (int i = 0; i < a.length || i < b.length; i++)
    {
        int temp = a.d[i] + b.d[i] + carry;
        c.d[c.length++] = temp % 10;
        carry = temp / 10;
    }
    if (carry != 0)
        c.d[c.length++] = carry;
    return c;
}

Big_Num sub(Big_Num& a,Big_Num& b)
{
    if (compare(a,b) == 0)
        std::swap(a, b);
    Big_Num c;

    for (int i = 0; i < a.length || i < b.length;i++)
    {
        if (a.d[i] < b.d[i])
        {
            a.d[i + 1] -= 1;
            a.d[i] += 10;
        }
        c.d[c.length++] = a.d[i] - b.d[i];
    }

    while (c.length > 0 && c.d[c.length-1] == 0)
        c.length--;

    return c;
}

Big_Num multi(Big_Num& a, int b)
{
    Big_Num c;
    int carry = 0;
    for (int i = 0; i < a.length;i++)
    {
        int temp = a.d[i] * b + carry;
        c.d[c.length++] = temp % 10;
        carry = temp / 10;
    }
    while (carry != 0)
    {
        c.d[c.length++] = carry % 10;
        carry /= 10;
    }
    return c;
}

Big_Num divide(Big_Num& a, int b, int& r)
{
    Big_Num c;
    c.length = a.length;
    for (int i = a.length - 1; i >= 0;i--)
    {
        r = r * 10 + a.d[i];
        if (r < b)
            c.d[i] = 0;
        else
        {
            c.d[i] = r / b;
            r %= b;
        }
    }

    while (c.length - 1 >= 1 && c.d[c.length-1] == 0)
    {
        c.length--;
    }
    return c;
}

void print(Big_Num& e)
{
    for (int i = e.length-1; i >=0 ;i--)
        std::cout << e.d[i];
    std::cout << std::endl;

}

int main()
{
    int c;
    Big_Num a, b;
    std::string str1;
    std::string str2;
    std::cin >> str1 >> c;
    transform(a, str1);
    //transform(b, str2);

    //Big_Num c = add(a, b);
    //Big_Num c = sub(a, b);
    //Big_Num d = multi(a, c);
    //print(d);
    int r = 0;
    Big_Num d = divide(a, c, r);
    print(d);

    system("pause");
    return 0;
}

// if (compare(a,b) == 1)
//     std::cout << "a>b" << std::endl;
// else if (compare(a,b) == 0)
//     std::cout << "a<b" << std::endl;
// else
//     std::cout << "a=b" << std::endl;

七.扩展欧几里得算法

跳过了,有想法的可以去看看

八.组合数
1.关于n!的问题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//关于n!的一个问题 求n!中有多少个质因子p
//寄有点麻烦,后续遇到再来查看,先就用暴力实现吧
#include <iostream>

int cal1(int n,int p)
{
    int ans = 0;
    for (int i = 2; i <= n;i++)
    {
        int temp = i;
        while (temp % p ==0)
        {
            ans++;
            temp /= p;
        }
    }
    return ans;
}


//思路：n/p + n/p^2 + n/p^3 + ···
//非递归实现
int cal2(int n,int p)
{
    int ans = 0;
    while (n)
    {
        ans += n / p;
        n /= p;
    }
    return ans;
}

//递归实现
int cal3(int n,int p)
{
    if (n<p)
        return 0;
    return n / cal3(n / p, p);
}
2.组合数

根据范围用不同的算法来实现,比较麻烦，碰到的时候再来看吧,一般情况下根据定义式的暴力方法应该足够了

1
2
3
4
5
6
7
8
9
10
11
12
13
//计算组合数 通过定义式 Cmn = n! / m!(n-m)!

long long GET_C(long long n, long long m)
{
    long long ans = 1;
    for (long long i = 1; i <= n;i++)
        ans *= i;
    for (long long i = 1; i <= m;i++)
        ans /= i;
    for (long long i = 1; i <= n - m;i++)
        ans /= i;
    return ans;
}

第六章 C++标准模板库(STL)介绍

一.std::vector
1
2
3
4
5
6
//1.push_back
//2.pop_back
//3.size
//4.clear
//5.insert    参数为迭代器
//6.erase     参数为迭代器
二.std::set
1
2
3
4
5
//1.insert 参数为模板参数
//2.find   返回一个迭代器 
//3.erase 参数为迭代器
//4.size
//5.clear
三.std::string
1
2
3
4
//1.substr(pos,len)
//2.string::npos find失配时的值
//3.find(str)   找子串
//4.replace(pos,len,str2)
四.std::map
1
2
3
4
5
6
//1.通过下标访问
//2.通过迭代器范围,迭代器的底层为一个std::pair
//3.find(key) 返回键值为key的映射的迭代器
//4.erase
//5.size
//6.clear
五.std::queue
1
2
3
4
5
6
//1.push
//2.front
//3.back
//4.pop
//5.empty
//6.size
六.priority_queue
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
#include <iostream>
#include <queue>
#include <vector>
#include <string>

struct fruit
{
    std::string name;
    int price;
    friend bool operator <(fruit a, fruit b)
    {
          return a.price < b.price;
    }
}f1,f2,f3;



int main()
{
    std::priority_queue<int> q1;
    std::priority_queue<int,std::vector<int>, std::greater<int> > q2;
    std::priority_queue<int,std::vector<int>, std::less<int> > q3;
    q1.push(2);
    q1.push(3);
    q1.push(1);

    q2.push(2);
    q2.push(3);
    q2.push(1);

    std::cout << q1.top() << std::endl;
    std::cout << q2.top() << std::endl;

    std::priority_queue<fruit> p;
    f1.name = "apple";
    f1.price = 2;
    f2.name = "orange";
    f2.price = 3;
    f3.name = "banana";
    f3.price = 1;

    p.push(f1);
    p.push(f2);
    p.push(f3);

    std::cout << p.top().name << ":" << p.top().price << std::endl;

    system("pause");
    return 0;
}
七.std::stack
1
2
3
4
5
//1.push
//2.pop
//3.top
//4.empty
//5.size
八.std::pair
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <map>
#include <iostream>

int main()
{
    int n;
    std::cin >> n;

    while (n--)
    {
        std::pair<double, double> ans(0,0);
        double input;
        for (int i = 0; i < 3;i++)
        {
            std::cin >> input;
            ans.first += input;
            std::cin >> input;
            ans.second += input;
        }
        printf("%.1lf %.1lf\n", (ans.first / 3), (ans.second / 3));
    }
    system("pause");
    return 0;
}
九.algorithm
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
//1.max min abs

//2.swap

//3.reverse
#include <iostream>
#include <algorithm>
#include <string>

int main()
{
    std::string temp;
    std::cin >> temp;

    std::reverse(temp.begin(), temp.end());
    std::cout << temp;

    system("pause");
    return 0;
}

//4.next_permutation
//给出一个序列的下一个全排列
#include <iostream>
#include <algorithm>
#include <string>

int main()
{
    // int a[3] = {1, 2, 3};
    // do{
    //     printf("%d%d%d\n", a[0], a[1], a[2]);
    // } while (std::next_permutation(a, a + 3));
    std::string input;

    while (std::cin >> input)
    {
        do{
            std::cout << input << std::endl;
        } while (std::next_permutation(input.begin(), input.end()));
    }

    system("pause");
    return 0;
}

//5.fill

//6.sort

//7.lower_bound() 和 upper_bound()
//二分查找章节4.5.1中自己实现过,就是在存在多个重复元素的序列中,利用这两个函数找到左下标和右下标

第七章 栈 队列 链表

第八章 DFS和BFS

1.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
#include <iostream>

int max_value = 0;

int n,all_weight;
int price[10], weight[10];

void DFS1(int index,int PSum,int WSum)
{
    if (index == n)
    {
        if (PSum > max_value && WSum <= all_weight)
        {
            max_value = PSum;
        }
        return;
    }
    DFS1(index + 1, PSum, WSum);
    DFS1(index + 1, PSum + price[index], WSum + weight[index]);
}

void DFS2(int index,int PSum,int WSum)
{
    if (index == n)
    {
        return;
    }
    DFS2(index + 1, PSum, WSum);

    if (WSum + weight[index] <= all_weight)
    {
        if (PSum + price[index] > max_value)
        {
            max_value = PSum + price[index];
        }
        DFS2(index + 1, PSum + price[index], WSum + weight[index]);
    }
}

int main()
{
    std::cin >> n >> all_weight;
    for (int i = 0; i < n;i++)
    {
        std::cin >> weight[i];
    }
    for (int i = 0; i < n;i++)
    {
        std::cin >> price[i];
    }
    DFS2(0,0,0);

    std::cout << max_value << std::endl;

    system("pause");
    return 0;
}
2.bfs

也拿迷宫举例的话,就是每个岔路口分出去不同的人去找出口,同时进行嘛,比起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
#include <iostream>
#include <map>
#include <queue>

std::pair<int, int> direction[4] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};

int count = 0;
int n = 0, m = 0;
int  matrix[10][10];
bool IsEnterQueen[10][10]{false};

bool check(int now_x, int now_y)
{
    return matrix[now_y][now_x] == 1 && now_x >= 0 && now_y >=0 && 
           now_x < n && now_y < m && IsEnterQueen[now_y][now_x] == false;
}

void BFS(int m, int n)
{
    std::queue<std::pair<int,int>> q;

    for (int i = 0; i < m;i++)
    {
        for (int j = 0; j < n;j++)
        {
            if (matrix[i][j] == 1 && IsEnterQueen[i][j] == false)
            {
                count++;
                q.push({j, i});
                while (!q.empty())
                {
                    auto now_deque = q.front();
                    q.pop();

                    for (int i = 0; i < 4;i++)
                    {
                        int now_x = now_deque.first + direction[i].first;
                        int now_y = now_deque.second + direction[i].second;

                        if (check(now_x,now_y))
                        {
                            q.push({now_x, now_y});
                            IsEnterQueen[now_y][now_x] = true;
                        }
                    }
                }
            }
        }
    }

}

int main()
{
    std::cin >> n >> m;
    for (int i = 0; i < m;i++)
    {
        for (int j = 0; j < n;j++)
        {
            std::cin >> matrix[i][j];
        }
    }
    BFS(m,n);
    std::cout << count << std::endl;
    system("pause");
    return 0;
}