发表更新C++算法4 分钟读完 (大约537个字)

Cpp算法-BFS

说明

本文实现只是框架，应当灵活运用，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
void bfs()
{
    int head = 1, tail = 2;
    vis[start_x][start_y] = true;            //标记起始点
    que[head][0] = start_x; 
    que[head][1] = start_y;                  //起始点入队
    while(head < tail)                       //队不为空
    {
        int x = que[head][0], y = que[head][1]  //获取队首点
        for (int i = 0; i < 子节点数; ++i)
        {
            int x2 = x子节点, y2 = y子节点;
            if (x2, y2满足条件 && !vis[x2][y2])
            {
                记录结果;
                vis[x2][y2] = true;
                que[tail][0] = x2;
                que[tail][0] = y2;
                tail++;                         //入队
            }
        }
        head++;                                 //队首出队
    }
    return
}

STL-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
struct Node
{
    int x, y;
}node, top;

queue<Node> que;

void bfs()
{
    vis[sx][sy] = true;
    node.x = sx;
    node.y = sy;
    que.push(node);
    ans[sx][sy] = 0;
    while(!que.empty())
    {
        top = que.front();
        for (int i = 0; i < 8; ++i)
        {
            int x2 = ..., y2 = ...;
            if (x2, y2满足条件 && !vis[x2][y2])
            {
                记录结果;
                vis[x2][y2] = true;
                node.x = x2;
                node.y = y2;
                que.push(node);
            }
        }
        que.pop();
    }
    return;
}

例

洛谷P1443

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<bits/stdc++.h>
using namespace std;

int n, m, sx, sy, vis[210][210], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

struct horse
{
    int x, y;
}node, top;

queue<horse> que;

void bfs()
{
    vis[sx][sy] = 1;
    node.x = sx;
    node.y = sy;
    que.push(node);
    ans[sx][sy] = 0;
    while(!que.empty())
    {
        top = que.front();
        for (int i = 0; i < 8; ++i)
        {
            int x2 = top.x + gox[i];
            int y2 = top.y + goy[i];
            if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
            {
                ans[x2][y2] = ans[top.x][top.y] + 1;
                vis[x2][y2] = 1;
                node.x = x2;
                node.y = y2;
                que.push(node);
            }
        }
        que.pop();
    }
    return;
}

int main()
{
    scanf("%d %d %d %d", &n, &m, &sx, &sy);
    memset(ans, -1, sizeof(ans));
    bfs();
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            printf("%-5d", ans[i][j]);
        printf("\n");
    }
    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
#include<bits/stdc++.h>
using namespace std;

int n, m, sx, sy, vis[210][210], que[50000][2], ans[210][210];
int gox[8] = {-2, -1, 1, 2, 2, 1, -1, -2};
int goy[8] = {1, 2, 2, 1, -1, -2, -2, -1};

void bfs()
{
    int head = 1, tail = 2;
    vis[sx][sy] = 1;
    que[head][0] = sx;
    que[head][1] = sy;
    ans[sx][sy] = 0;
    while (head < tail)
    {
        int x, x2, y, y2;
        x = que[head][0];
        y = que[head][1];
        for (int i = 0; i < 8; ++i)
        {
            x2 = x + gox[i];
            y2 = y + goy[i];
            if (x2 >= 1 && x2 <= n && y2 >= 1 && y2 <= m && !vis[x2][y2])
            {
                ans[x2][y2] = ans[x][y] + 1;
                vis[x2][y2] = 1;
                que[tail][0] = x2;
                que[tail][1] = y2;
                tail++;
            }
        }
        head++;
    }
    return;
}

int main()
{
    scanf("%d %d %d %d", &n, &m, &sx, &sy);
    memset(ans, -1, sizeof(ans));
    bfs();
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 1; j <= m; ++j)
            printf("%-5d", ans[i][j]);
        printf("\n");
    }
    return 0;
}
发表更新C++算法2 分钟读完 (大约227个字)

Cpp算法-DFS

说明

本文实现只是框架，应当灵活运用，dfs(…)函数返回值类型、参数列表根据情况灵活更改

框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(参数列表)
{
    if (到达目的地) 输出结果;
    else
    {
        for (int i = 0; i < 行动方法数; ++i)
        {
            if (下一步可行)
            {
                记录此步;
                dfs(改动后的参数列表);
                取消记录此步;
            }
        }
    }
    return;
}

例

洛谷P1605

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<bits/stdc++.h>
using namespace std;

int n, m, t, sx, sy, fx, fy, ans;
int mg[6][6], now[6][6];
int go[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

void dfs(int x, int y)
{
    int x2, y2;
    if (x == fx && y == fy) ans++;
    else
    {
        for (int i = 0; i < 4; ++i)
        {
            x2 = x + go[i][0];
            y2 = y + go[i][1];
            if (x2 > 0 && x2 <= n && y2 > 0 && y2 <= m && mg[x2][y2] == 0 && now[x2][y2] == 0)
                
            {
                now[x2][y2] = 1;
                dfs(x2, y2);
                now[x2][y2] = 0;
            }
        }
    }
    return;
}

int main()
{
    memset(mg, 0, sizeof(mg));
    scanf("%d %d %d", &n, &m, &t);
    scanf("%d %d %d %d", &sx, &sy, &fx, &fy);
    for (int i = 1; i <= t; ++i)
    {
        int x, y;
        scanf("%d %d", &x, &y);
        mg[x][y] = 1;
    }
    now[sx][sy] = 1;
    ans = 0;
    dfs(sx, sy);
    printf("%d", ans);
    return 0;
}
BiliBili主页

最新文章

归档

标签

AtCoder1
CSP-S2
CTF16
Cpp67
Haskell11
Linux1
Luogu5
NOIp33
Python1
Rust2
SPOJ1
Writeup11
bfs1
blog2
bug2
dsu on tree1
git1
github3
hexo1
manim3
markdown3
mkdocs1
python5
图论2
学习1
左偏树1
差分约束1
并查集1
数据结构4
数论3
最大流1
最短路2
杂谈2
树状数组1
游记1
状态压缩1
生活3
笔记29
算法32
线段树1
网络流22
范畴论1
莫队5
计算几何1
费用流10
随笔3
题解36

分类

×