AT46 リモコン

URL: 洛谷

题目描述:

搜索的裸题,只不过操作有点多,略烦。

思路:

看到其他大佬都在用dfs,迭代加深,打表,贪心等神奇算法,蒟蒻只得给出一个标准模板(怎么还有用结构体的……完全不用啊)

使用bfs求最短路径,因为数据小可以通过,只不过在push的时候要写6个if,烦。

最后注意下输出要换行。

代码:

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<bits/stdc++.h>
using namespace std;
typedef long long ll;
queue<ll> q;
bool vis[41];
ll a,b,dis[41];
int main(){
scanf("%lld%lld",&a,&b);
q.push(a);
vis[a]=1;
dis[a]=0;
while(!q.empty()){
int now=q.front();
if(now==b) {
printf("%lld\n",dis[now]);
return 0;
}
if(!vis[now-1]&&now-1>=0) vis[now-1]=1,q.push(now-1),dis[now-1]=dis[now]+1;
if(!vis[now+1]&&now+1<=40) vis[now+1]=1,q.push(now+1),dis[now+1]=dis[now]+1;
if(!vis[now-5]&&now-5>=0) vis[now-5]=1,q.push(now-5),dis[now-5]=dis[now]+1;
if(!vis[now+5]&&now+5<=40) vis[now+5]=1,q.push(now+5),dis[now+5]=dis[now]+1;
if(!vis[now-10]&&now-10>=0) vis[now-10]=1,q.push(now-10),dis[now-10]=dis[now]+1;
if(!vis[now+10]&&now+10<=40) vis[now+10]=1,q.push(now+10),dis[now+10]=dis[now]+1;
q.pop();
}
return 0;
}