牛客小白月赛22- 收集纸片

题目链接:https://ac.nowcoder.com/acm/contest/4462/D

在这里插入图片描述

思路

因为菜所以才参加小白月赛,这题,题目读完应该就晓得是一道搜索(不排除有更好的方法QAQ), 这题搞了我半天,错在于求最短的距离我写成了

1
abs(ve[i - 1].x - ve[j - 1].x) + abs(ve[i - 1].y - ve[j - 1].y);

题目规定了只能沿着x轴,y轴移动,所以得这样求

1
abs(ve[i - 1].x - ve[j - 1].x) + abs(ve[i - 1].y - ve[j - 1].y);

emmmm,可能是打着打着想睡了,QAQ

代码

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
#include <bits/stdc++.h>
using namespace std;
struct node
{
int x;
int y;
}you;
unordered_map<int, unordered_map<int, int> > mp;
unordered_map<int, int> vis;
int minn;
int vit[15];
int n, m, t, k;
void dfs(int now, int cnt, int sum) {
// cout << now << " " << cnt << " " << sum << endl;
if(cnt == k) {
minn = min(minn, sum + vis[now]);
return ;
}
for(int i = 1; i <= k; i++){
if(vit[i]) continue;
vit[i] = 1;
dfs(i, cnt + 1, sum + mp[now][i]);
vit[i] = 0;
}
}
int main()
{
ios::sync_with_stdio(false);
fill(vit, vit + 15, 0);
cin >> t;
while(t--){
cin >> n >> m;
cin >> you.x >> you.y;
vector<node> ve;
ve.clear();
mp.clear();
vis.clear();
cin >> k;
int sum = 0;
for(int i = 1; i <= k; i++){
int a, b;
cin >> a >> b;
// 题目说明了不会存在纸片在房间外面所以没必要写,但写了增加啥来着,忘了QAQ
if(a > n || a < 1 || b > m || b < 1) continue;
sum++;
ve.push_back(node{a, b});
}
k = sum;
for(int i = 1; i <= k; i++){
for(int j = i; j <= k; j++){
if(i == j) continue;
mp[i][j] = mp[j][i] = abs(ve[i - 1].x - ve[j - 1].x) + abs(ve[i - 1].y - ve[j - 1].y);
}
vis[i] = abs(ve[i - 1].x - you.x) + abs(ve[i - 1].y - you.y);
}
minn = n * m;
for(int i = 1; i <= k; i++){
vit[i] = 1;
dfs(i, 1, vis[i]);
vit[i] = 0;
}

cout << "The shortest path has length " << minn << endl;
}
return 0;
}

本文标题:牛客小白月赛22- 收集纸片

文章作者:HKer_YM

发布时间:2020年02月23日 - 12:56:16

最后更新:2020年03月01日 - 18:13:41

原始链接:https://blog.dreams-wj.top/2020/02/23/%E7%89%9B%E5%AE%A2%E5%B0%8F%E7%99%BD%E6%9C%88%E8%B5%9B22-%E6%94%B6%E9%9B%86%E7%BA%B8%E7%89%87/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。