Luobuyu's Blog

0%

搜索路径

发表于 分类于 热度： ℃ 评论：
本文字数： 1.6k 阅读时长 ≈ 1 分钟
。。。。。

与寻路有关的路径记录问题

之前我使用 BFS 寻路的时候都是手写队列，然后给 Node 增加一个 pre 属性来记录前一个点在数组中的位置。

现在发现也可以直接建立一个和图结构一样的新数组 pre ，注意数组的维度要和 Node 中的保持一致 ，然后使用 Node 中的属性作为下标，pre 中的属性作为 Node 的前一个点

dp有关的问题，可以记录当前位置选了几个，也可以记录前一个位置，然后两者作差，得到当前位置选了几个。

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
using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e3 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn][maxn];
bool vis[maxn][maxn];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
struct Node
{
    int x, y;
};
queue<Node> q;
Node pre[maxn][maxn];
/**
 * 好久没写过路径问题了，需要记录每个点的pre，
 * 最好是使用和原图一样的数据结构记录
 * 
 * 
 **/
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    read(n);
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            read(a[i][j]);
        }
    }
    int cnt = 0;
    int ans = 0;
    q.push({0, 0});
    pre[0][0] = {-1, -1};
    vis[0][0] = 1;
    while (!q.empty())
    {
        auto u = q.front();
        q.pop();
        if ((u.x == n - 1) && (u.y == n - 1))
        {
            break;
        }
        for (int i = 0; i < 4; i++)
        {
            int newx = u.x + dx[i];
            int newy = u.y + dy[i];
            if (newx < 0 || newx >= n || newy < 0 || newy >= n || a[newx][newy] == 1 || vis[newx][newy] == 1)
                continue;
            vis[newx][newy] = 1;
            q.push({newx, newy});
            pre[newx][newy] = {u.x, u.y};
        }
    }
    stack<Node> s;
    int x = n - 1, y = n - 1;
    s.push({x, y});
    while (pre[x][y].x != -1 && pre[x][y].y != -1)
    {
        s.push(pre[x][y]);
        int tmpx = pre[x][y].x;
        int tmpy = pre[x][y].y;
        x = tmpx;
        y = tmpy;
    }

    while (!s.empty())
    {
        auto x = s.top();
        printf("%d %d\n", x.x, x.y);
        s.pop();
    }

    return 0;
}