BD202311夏日漫步（最少步数，BFS或者 Dijstra）
原创 已于 2024-04-14 16:08:07 修改 · 粉丝可见 · 610 阅读 · 5 · 7 · 本内容遵循CC 4.0 BY-SA版权协议 版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。 GEO检测 · 编辑
文章链接：https://blog.csdn.net/hacker_51/article/details/137709566
本题链接： 码蹄集
题目：
夏日夜晚，小度看着庭院中长长的走廊，萌发出想要在上面散步的欲望，小度注意到月光透过树荫落在地砖上，并且由于树荫的遮蔽度不通，所以月光的亮度不同，为了直观地看到每个格子的亮度，小度用了一些自然数来表示它们的亮度。亮度越高则数字越大，亮度相同的数字相同。
走廊是只有一行地砖的直走廊。上面一共有 n 个格子，每个格子都被小度给予了一个数字 $$
a_{i}
$$ 来表示它的亮度。
小度现在站在 1 号格子，想要去到 n 号格子。小度可以正向或反向移动到相邻的格子，每次需要花费 1 的体力。
同时小度还有瞬移的能力， 其可以花费 1 的体力来瞬移到与当前格子亮度相同的格子上 。而且由于小度视野有限，只能瞬移到在 当前格子后的第一次亮度相同的格子 上。这也意味着 不能反向瞬移 。
小度想知道，到达 n 号格子需要花费的最小体力是多少。以此制定一个最优秀的散步方案。
样例：
cobol<br/>6<br/>0 1 2 3 1 5<br/> |
思路：
根据题意，我们将小度移动方向，看成一块图，相邻格子之间作为路线，连接线，我们就可以很方便的，根据BFS或者 Dijkstra 来获取最少步数的操作了。
注意！以后遇到最少步数，最少操作这些关键字，思路得要联想到 BFS 和 Dijkstra 这些最少操作数方面的算法啦！
Dijstra代码详解如下：
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
| #include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define INF 0x3f3f3f3f3f3f
#define umap unordered_map
#define uset unordered_set
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e5 + 10;
inline void solve();
signed main()
{
IOS;
int _t = 1;
while (_t--)
{
solve();
}
return 0;
}
int n,ans;
using PII = pair<int,int>;
umap<int,vector<int>>g,cnt;
inline void Dijkstra()
{
vector<int>dist(n + 1,INF);
vector<bool>st(n + 1,false);
dist[0] = 0;
priority_queue<PII,vector<PII>,greater<PII>>q;
q.emplace(PII(0,0));
while(q.size())
{
PII now = q.top();
q.pop();
if(st[now.y])continue;
st[now.y] = true;
int a = now.y,dis = now.x;
for(int i = 0;i < (int)g[a].size();++i)
{
int j = g[a][i];
if(dist[j] > dis + 1) dist[j] = dis + 1;
q.emplace(PII(dist[j],j));
}
}
ans = dist[n - 1];
}
inline void solve()
{
cin >> n;
uset<int>node;
for(int i = 0,x;i < n;++i)
{
cin >> x;
node.emplace(x);
cnt[x].emplace_back(i);
if(i - 1 >= 0)
{
g[i].emplace_back(i - 1);
g[i - 1].emplace_back(i);
}
}
for(auto &i:node)
{
for(int j = 0;j + 1 < (int)cnt[i].size();++j)
{
g[cnt[i][j]].emplace_back(cnt[i][j + 1]);
}
}
Dijkstra();
cout << ans << endl;
}
|
最后提交：
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
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
| #include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define x first
#define y second
#define int long long
#define YES puts("YES")
#define NO puts("NO")
#define INF 0x3f3f3f3f3f3f
#define umap unordered_map
#define uset unordered_set
#define All(x) x.begin(),x.end()
#pragma GCC optimize(3,"Ofast","inline")
#define IOS std::ios::sync_with_stdio(false),cin.tie(0), cout.tie(0)
using namespace std;
const int N = 2e5 + 10;
inline void solve();
signed main()
{
IOS;
int _t = 1;
while (_t--)
{
solve();
}
return 0;
}
int n,ans;
using PII = pair<int,int>;
umap<int,vector<int>>g,cnt;
inline int BFS()
{
vector<bool>st(N,false);
queue<int>q;
int step = 0;
q.emplace(0);
while(q.size())
{
int sz = q.size();
while(sz--)
{
int now = q.front();
q.pop();
st[now] = true;
if(now == n - 1) return step;
for(int i = 0;i < (int)g[now].size();++i)
{
int j = g[now][i];
if(!st[j])
{
st[j] = true;
q.emplace(j);
}
}
}
++step;
}
return 0;
}
inline void solve()
{
cin >> n;
uset<int>node;
for(int i = 0,x;i < n;++i)
{
cin >> x;
node.emplace(x);
cnt[x].emplace_back(i);
if(i - 1 >= 0)
{
g[i].emplace_back(i - 1);
g[i - 1].emplace_back(i);
}
}
for(auto &i:node)
{
for(int j = 0;j + 1 < (int)cnt[i].size();++j)
{
g[cnt[i][j]].emplace_back(cnt[i][j + 1]);
}
}
int ans = BFS();
cout << ans << endl;
}
|
最后提交：
